质数与约数

什么是质数

在大于1的整数中，约数只有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
   }

分解质因数

1. 试除法分解质因数 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()
}