质数

[meishaoming]

1

什么是质数？

• 它是大于 1 的自然数
• 只能被 1 和它自己整除

所以怎么判断 n 是不是质数？

依次从集合 [2 .. n-1] 中取一个数记为 i，如果 n/i 的余数都不为 0，那么 n 就是质数。

取余数用模运算，所以代表可表示为：

        def is_prime(x):
            for i in range(2, x):
                if x % i == 0:
                    return False
            return True

对于一个 n，最糟糕的情况下（它是一个质数）要做 n-2 次模运算才能得出结果，时间复杂度为 O(1) 。

如果要取 n 以内的所有质数，对 [2..n-1] 的每个数做一次 is_prime() 判断，要做 n-2 次。所以总的时间复杂度为 O(n^2) 。

class Solution:
    def countPrimes(self, n: int) -> int:

        def is_prime(x):
            for i in range(2, x):
                if x % i == 0:
                    return False
            return True

        ans = []
        for x in range(2, n):
            if is_prime(x):
                ans.append(x)
        return len(ans)

2

7 是一个质数，按上边的算法，会依次模 [ 2, 3, 4, 5, 6 ] 。有必要算这么多吗？

没有。对于任一个大于 7/2 的数（比如 4、5、6）来说，比如 7 除以它肯定除不尽，有余数。

即对于 n 来说，如果 n/2 < x < n，那么 1 < n/x < 2 ，除完的结果肯定不是一个整数。所以没有必要算了。所以从 2 一直尝试到 n/2 （包括n/2）即可。

于是 is_prime() 改为：

        def is_prime(x):
            for i in range(2, x//2+1):
                if x % i == 0:
                    return False
            return True

3

sqrt(x) * sqrt(x) = x ，所以 x 的一对因数中有一个一定小于 sqrt(x)。

举例：100 的因数对：1x100, 2x50, 4x25, 5x20, 10x10 。每一对中肯定有一个 <= 10 ，即 sqrt(100)

所以检查 [1..sqrt(x)] 即可。

        def is_prime(x):
            for i in range(2, sqrt(x)+1):
                if x % i == 0:
                    return False
            return True

4

比如 101，只需要检查小于 10 的奇数即可，即 3，5，7，9 。但 9 是多于的，因为已经检查过 3 了。

只需要检查小于 sqrt(x) 的质数。

primes[..] && i < sqrt(x)

class Solution:
    def countPrimes(self, n: int) -> int:
        from math import sqrt
        def is_prime(x):
            for i in primes:
                if i > int(sqrt(x)):
                    return True
                if x % i == 0:
                    return False
            return True
        if n <= 2:
            return 0
        primes = [ 2 ]
        for x in range(3, n):
            if is_prime(x):
                primes.append(x)
        return len(primes)

5 筛法

class Solution:
    def countPrimes(self, n: int) -> int:
        if n <= 2: return 0
        primes = [1]*n
        primes[0] = primes[1] = 0
        primes[2] = 1
        for i in range(2, n):
            if primes[i]:
                for j in range(i*2, n, i):
                    primes[j] = 0
        return sum(primes)

筛法中也只需要算到 int(sqrt(x)) 。

class Solution:
    def countPrimes(self, n: int) -> int:
        if n <= 2: return 0
        from math import sqrt
        primes = [1]*n
        primes[0] = primes[1] = 0
        primes[2] = 1
        for i in range(2, int(sqrt(n))+1):
            if primes[i]:
                for j in range(i*2, n, i):
                    primes[j] = 0
        return sum(primes)

sqrt(n) 可以写成 n*0.5，循环清 0 可以直接写成 `primes[ii:n:i] = [0] len(primes[ii:n:i])`

class Solution:
    def countPrimes(self, n: int) -> int:
        if n <= 2: return 0
        primes = [1]*n
        primes[0] = primes[1] = 0
        primes[2] = 1
        for i in range(2, int(n**0.5)+1):
            if primes[i]:
                primes[i*i:n:i] = [0] * len(primes[i*i:n:i])
        return sum(primes)