寻找质数（prime number）

如果一个正整数，它只能被1和它自己整除，那么，它就是一个质数，也称为素数，英文叫prime number。

下面这个算法的思路是我昨天中午午休时睡不着，突然灵机一动的成果。

如果\(N \neq 2 \cdot M\)，那么在\((\left\lceil\frac{N}{2}\right\rceil,N)\)这个区间内，不存在因数。

假设在上述区间存在一个因数，那么这个因数一定是\(\frac{N}{2}\)，矛盾。

如果\(N \neq 3 \cdot M\)，那么在\((\left\lceil\frac{N}{3}\right\rceil,N)\)这个区间内，不存在因数。

假设在上述区间存在一个因数，那么这个因数一定是\(\frac{N}{3}\)，矛盾。

按照这个思路，代码每尝试一个数是否为因数，后续尝试的范围就会缩小。

当一个数不能被2整除的时候，其实我们是没有必要再用4来做整除测试，4不是质数。代码在使用某个数做整除判断的时候，可以只使用前面已经判断出来的，较小的质数。

$ cat test_prime.py
import sys


print(2)
print(3)
print(5)
pn = [5]
i = 5
while True:
    i += 2  # skip even number
    # check if can ben divided by 3
    if sum(list(map(int,list(str(i))))) % 3 == 0:
        continue
    idx = -1
    pn_len = len(pn)
    found = False
    while True:
        idx += 1
        if idx == pn_len or pn[idx] > i//pn[idx]:
            found = True
            break
        if i%pn[idx] == 0:
            break
    if found:
        pn.append(i)
        print(i)
        # stupid check
        for j in range(2, i):
            if i%j == 0:
                print('bad algo...')
                sys.exit(1)
    else:
        # stupid check
        for j in range(2, i):
            if i%j == 0:
                break
        else:
            print('bad algo... omit', i)
            sys.exit(2)

这个算法跑得挺快的，但如果一直运行下去，最终pn这个list会吃掉所有的内存。可以不适用pn这个list，即不记录前面已经找到的质数，用一个循环+1的变量来做除法判断。把这个算反的一部分抠出来，可以实现快速判断某一个数是否为质数的接口，但是不要使用pn这个list。