找质数

问题

找出正整数 n 以内的所有质数。

质数，也叫素数，即除了1和自身外无法被其它数整除的大于1的数，如7，只能被1和7整除。质数在算法问题中很常见。

解法

暴力查找法

假设一个数不是质数，则能把它整除的数一定在 \([2,\sqrt{n}]\) 这个较小的范围之内。

import math

def get_primes(n):
    if n < 2:
        return
    yield 2
    for i in range(3, n):
        is_prime = True
        for j in range(2, int(math.sqrt(i)) + 1):
            if i % j == 0:
                is_prime = False

        if is_prime:
            yield i

if __name__ == '__main__':
    primes = [x for x in get_primes(20)]
    # 输出 [2, 3, 5, 7, 11, 13, 17, 19]
    print(primes)

非2,3,5,7的倍数

假设一个数不是质数，则它一定是 2,3,5,7 中的至少一个的倍数。

def get_primes(n):
    f = lambda x: x % 2 != 0 and x % 3 != 0 and x % 5 != 0 and x % 7 != 0
    if n < 2:
        return
    for i in range(2, n + 1):
        if i in (2, 3, 5, 7):
            yield i
        else:
            if f(i):
                yield i

if __name__ == '__main__':
    primes = [x for x in get_primes(20)]
    # 输出 [2, 3, 5, 7, 11, 13, 17, 19]
    print(primes)

使用容器标记

此方法本质上还是用到了上面的思想，一个质数不能是 2,3,5,7 的倍数，用一个容器标记 n 以内的各个数是否是质数。标记为质数的元素的索引即是质数。

def get_primes(n):
    boxes = [True] * n
    boxes[0] = False  # 0 和 1 不是质数
    boxes[1] = False

    for i in (2, 3, 5, 7):
        # 最小质数的倍数标记为不是质数
        pointer = i * 2
        while pointer < n:
            boxes[pointer] = False
            pointer += i

    return [idx for idx, value in enumerate(boxes) if value]


if __name__ == '__main__':
    primes = get_primes(20)
    print(primes)

上面的过程释义如下，用 √ 标记质数：

初始化， 0 和 1 不是质数：

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

2 的倍数不是质数：

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

3的倍数不是质数：

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

5的倍数不是质数：

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

7的倍数不是质数：

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

剩下的 2,3,5,7,11,13,17,19 即为质数。