质数与约数

什么是质数

在大于1的整数中，约数只有1和本身，那么这个数就是质数，或者叫素数。

质数的判定

试除法 O(sqrt(n))，当然对于约数是成对出现即（d, x/d), 因此对于最大的约数d满足 d <= sqrt(x), 考虑到sqrt每次都要去调用函数计算，因此可以s

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

func main() {
    var reader = bufio.NewReader(os.Stdin)
    var n = readInt(reader)
    for i := 0; i < n; i++ {
        var num = readInt(reader)
        fmt.Println(okString(num))
    }
}

func okString(num int) string {
    if ok(num) {
        return "Yes"
    }
    return "No"
}

func ok(num int) bool {
    if num <= 1 {
        return false
    }

    for i := 2; i < num/i+1; i++ {
        if num%i == 0 {
            return false
        }
    }
    return true
}

func readLine(reader *bufio.Reader) string {
    var line, _ = reader.ReadString('\n')
    return strings.TrimRight(line, "\n")
}

func readInt(reader *bufio.Reader) int {
    var a, _ = strconv.Atoi(readLine(reader))
    return a
}

func readArray(reader *bufio.Reader, sep string) []int {
    var line = readLine(reader)
    var strList = strings.Split(line, sep)
    var nums = make([]int, 0)
    var err error
    var v int
    for i := 0; i < len(strList); i++ {
        if v, err = strconv.Atoi(strList[i]); err != nil {
            continue
        }
        nums = append(nums, v)
    }
    return nums
}

分解质因数

试除法分解质因数 O(sqrt(n))；O(logn) ~ O(sqrt(n))

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

func main() {
    var reader = bufio.NewReader(os.Stdin)
    var n = readInt(reader)
    for i := 0; i < n; i++ {
        var num = readInt(reader)
        divide(num)
    }
}

func divide(num int) {
    for i := 2; i < num/i+1; i++ {
        if num%i != 0 {
            continue
        }

        var cnt int
        for num%i == 0 {
            num /= i
            cnt++
        }
        fmt.Printf("%d %d\n", i, cnt)
    }
    if num > 1 {
        fmt.Printf("%d %d\n", num, 1)
    }
    fmt.Println()
}

func readLine(reader *bufio.Reader) string {
    var line, _ = reader.ReadString('\n')
    return strings.TrimRight(line, "\n")
}

func readInt(reader *bufio.Reader) int {
    var a, _ = strconv.Atoi(readLine(reader))
    return a
}

func readArray(reader *bufio.Reader, sep string) []int {
    var line = readLine(reader)
    var strList = strings.Split(line, sep)
    var nums = make([]int, 0)
    var err error
    var v int
    for i := 0; i < len(strList); i++ {
        if v, err = strconv.Atoi(strList[i]); err != nil {
            continue
        }
        nums = append(nums, v)
    }
    return nums
}

筛质数

朴素筛法

对于质数cnt++，对于每个数，将其倍数即为非质数

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

func main() {
    var nums = make([]*struct{}, 1000010)
    var cnt int
    var reader = bufio.NewReader(os.Stdin)
    var n = readInt(reader)
    for x := 2; x < n+1; x++ {
        if nums[x] == nil {
            cnt++
        }
        var t = 2 * x
        for t <= n {
            nums[t] = &struct{}{}
            t += x
        }
    }
    fmt.Println(cnt)
}

func readLine(reader *bufio.Reader) string {
    var line, _ = reader.ReadString('\n')
    return strings.TrimRight(line, "\n")
}

func readInt(reader *bufio.Reader) int {
    var a, _ = strconv.Atoi(readLine(reader))
    return a
}

func readArray(reader *bufio.Reader, sep string) []int {
    var line = readLine(reader)
    var strList = strings.Split(line, sep)
    var nums = make([]int, 0)
    var err error
    var v int
    for i := 0; i < len(strList); i++ {
        if v, err = strconv.Atoi(strList[i]); err != nil {
            continue
        }
        nums = append(nums, v)
    }
    return nums
}

埃氏筛法

由算术基本定理，只需要筛除质数的倍数元素即可。就是说对于非质数continue，对于质数那么则需要标记其倍数为非质数。

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

func main() {
    var nums = make([]*struct{}, 1000010)
    var cnt int
    var reader = bufio.NewReader(os.Stdin)
    var n = readInt(reader)
    for x := 2; x < n+1; x++ {
        if nums[x] != nil {
            continue
        }
        cnt++
        var t = 2 * x
        for t <= n {
            nums[t] = &struct{}{}
            t += x
        }
    }
    fmt.Println(cnt)
}

func readLine(reader *bufio.Reader) string {
    var line, _ = reader.ReadString('\n')
    return strings.TrimRight(line, "\n")
}

func readInt(reader *bufio.Reader) int {
    var a, _ = strconv.Atoi(readLine(reader))
    return a
}

func readArray(reader *bufio.Reader, sep string) []int {
    var line = readLine(reader)
    var strList = strings.Split(line, sep)
    var nums = make([]int, 0)
    var err error
    var v int
    for i := 0; i < len(strList); i++ {
        if v, err = strconv.Atoi(strList[i]); err != nil {
            continue
        }
        nums = append(nums, v)
    }
    return nums
}

线性筛法

对于一个非质数只会被它的最小质因子筛掉

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

func main() {
    var nums = make([]*struct{}, 1000010)
    var cnt int
    var zs = make([]int, 1000010)
    var reader = bufio.NewReader(os.Stdin)
    var n = readInt(reader)
    for x := 2; x < n+1; x++ {
        if nums[x] == nil {
            zs[cnt] = x
            cnt++
        }

        // 枚举质因数
        for t := 0; zs[t] <= n/x; t++ {
            nums[zs[t]*x] = &struct{}{}
            if x%zs[t] == 0 { // zs[t]一定是x的最小质因子，zs[t]一定是zs[t]*x的最小质因子
                break
            } // else { // zs[t]一定小于的所有质因子，zs[t]也一定是zs[t]*x的最小质因子
        }
    }
    fmt.Println(cnt)
}

func readLine(reader *bufio.Reader) string {
    var line, _ = reader.ReadString('\n')
    return strings.TrimRight(line, "\n")
}

func readInt(reader *bufio.Reader) int {
    var a, _ = strconv.Atoi(readLine(reader))
    return a
}

func readArray(reader *bufio.Reader, sep string) []int {
    var line = readLine(reader)
    var strList = strings.Split(line, sep)
    var nums = make([]int, 0)
    var err error
    var v int
    for i := 0; i < len(strList); i++ {
        if v, err = strconv.Atoi(strList[i]); err != nil {
            continue
        }
        nums = append(nums, v)
    }
    return nums
}

什么是约数

一个数x的约数指的是可以被x整除的数

约数个数：对于一个数N=(p1^a1) * (p2^a2) * ... * (pk^ak)，他的约数个数为(a1+1)*(a2+1)*...*(ak+1)，它的各约数的和为(p1^0 + p1^1 + ... + p1^a1) + ... + (pk^0 + pk^1 + ... + pk^ak)

一个数的所有约数

试除法求一个数的约数

package main

import (
    "bufio"
    "fmt"
    "os"
    "sort"
    "strconv"
    "strings"
)

func main() {
    var reader = bufio.NewReader(os.Stdin)
    var n = readInt(reader)
    for i := 0; i < n; i++ {
        var num = readInt(reader)
        fmt.Println(nums2string(getAns(num), " "))
    }
}

func getAns(num int) []int {
    var ans []int
    var i = 1
    for ; i < num/i; i++ {
        if num%i == 0 {
            ans = append(ans, i)
            ans = append(ans, num/i)
        }
    }
    if num == i*i {
        ans = append(ans, i)
    }
    sort.Ints(ans)
    return ans
}

func readLine(reader *bufio.Reader) string {
    var line, _ = reader.ReadString('\n')
    return strings.TrimRight(line, "\n")
}

func readInt(reader *bufio.Reader) int {
    var a, _ = strconv.Atoi(readLine(reader))
    return a
}

func readArray(reader *bufio.Reader, sep string) []int {
    var line = readLine(reader)
    var strList = strings.Split(line, sep)
    var nums = make([]int, 0)
    var err error
    var v int
    for i := 0; i < len(strList); i++ {
        if v, err = strconv.Atoi(strList[i]); err != nil {
            continue
        }
        nums = append(nums, v)
    }
    return nums
}

func nums2string(x []int, sep string) string {
    var b strings.Builder
    for i := 0; i < len(x); i++ {
        b.WriteString(strconv.Itoa(x[i]))
        b.WriteString(sep)
    }
    return b.String()
}

最后更新于4年前

这有帮助吗？