忆の風

Alg | 质数

判定质数/计算个数

质数定义

 质数是指在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数。

朴素 ->O(n)

  1. 小于 2 的数都不是质数
  2. 如果 2-n 中的数能把 n 整除，说明不是质数

优化 ->O(sqrt(n))

  1. 因数是成对出现的，若 d|n ,则有 n/d | n.
  2. 所以 d≤nd  ⟹  d2≤n  ⟹  d≤nd \leq \frac{n}{d} \implies d^{2}\leq n \implies d \leq \sqrt{n}

Code

朴素优化 筛法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func isPrime(n int) bool {
	if n < 2 {
		return false
	}
	for i := 2; i <= n/i; i++ {
		if n%i == 0 {
			return false
		}
	}
	return true
}

Erato 筛法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

var (
    st     [N]bool
    cnt    int
    primes [N]int
)

func Init(n int) {
    for i := 2; i <= n; i++ {
        if !st[i] { // 如果没被筛，是质数，存
            primes[cnt] = i
            cnt++
        }

        // 把i 的倍数全筛了
        for j := i; j <= n/i; j++ {
            st[j*i] = true
        }
    }
}

线性筛法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func getPrimes(n int) {
	for i := 2; i <= n; i++ {
		if !st[i] {
			primes[cnt] = i
			cnt++
		}

		for j := 0; i*primes[j] <= n; j++ {
			st[i*primes[j]] = true
			if i%primes[j] == 0 {
				break
			}
		}
	}
}

质因数分解

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func divide(n int) {
	for i := 2; i <= n/i; i++ {
		if n%i == 0 {
			s := 0
			for n%i == 0 {
				n /= i
				s++
			}
			fmt.Printf("%d %d\n", i, s)
		}
	}
	if n > 1 {
		fmt.Printf("%d %d\n", n, 1)
	}
}