线性素数筛选（linear sieve for prime number）_程序人生

偶然发现了这个和stackoverflow很像的地方。打算写些专栏，一方面，记录自己学到的东西。另一方面，也把这些分享给大家。无论是内容错误还是解释方式不好，都欢迎各位拍砖。转载到其他平台前也请通知我。

本篇的IDE是Pycharm，使用的是Python 3 的基本interpreter

问题起源

这个问题起源于我在想寻找最大素数的时候诞生的。出现这个问题，一开始的想法是通过暴力破解来达成目的，举例的话，就以寻找第20000个素数开始吧

算法演绎

import time

def func(num):
    # since once i larger than num//2, num will not be divisible by any i increment
    for i in range(2, num//2+1):
        if num % i == 0:
            return 0
    return 1

def find_prime():
    num = 1
    count = 0
    # find the 20000th prime in the world!
    primeCount = 20000
    while count < primeCount :
        num += 1
        count = func(num)+count
    return num

# count time
start = time.time()
num = find_prime()
end = time.time() -start
print(\"find %s in %s seconds\" % (num,end))

结果是:

find 224737 in 151.33826684951782 seconds

Process finished with exit code 0

151秒，感觉花了好长时间，显然这不是一个有效率的方法。

算法分析

由于我们每次寻找的素数时，都从2开始，逐渐上除，最后到num/2为止，确认是否是素数。那所用的效率就是
$$ O(N^2) $$

查找了一些文献以后，看到了一种方法:线性素数筛选:埃拉托斯特尼筛法（Sieve of Eratosthenes）

在每次我们确定素数的时候，将其之后的有关合数进行排除，每一次在寻找下个素数时，必然能一次性找到，而不用逐渐去加1来寻找。接着继续排除其有关合数。那这样所用效率就变成了
$$O(N*log(log(N)))$$
这里第一个N来自于寻找下个素数，而log(log(N)来自于寻找各个素数的合数，而这个算法，也需要一个$$O(N)$$的存储空间，我这里用了5000000的存储空间。而这是一个伪的polynomial算法。
wiki中显示了一种优化方法，可以在$$O(N)$$中完成，但相对的需要$$O(n^{1/2}\\log\\log n/\\log n)$$的存储空间。这里给予链接，Paul Pritchard

算法演绎

def fast_find_prime(n,limit =5000000):
    if limit %2 != 0 :
        limit+=1
    # Assume all numbers are prime number
    primes = [True] *limit
    # Eliminate 0 and 1
    primes[0], primes[1] = [None] *2
    # set count
    count = 0
    # enumerate numbers
    for ind, val in enumerate(primes):
        if val is True:
            # set number false when it is not prime
            # ind will skip not prime numbers
            primes[ind*2::ind] = [False] * (((limit-1)//ind)-1)
            count += 1
        if count == n: return  ind
    return False

#count time
start = time.time()
num = fast_find_prime(20000)
end = time.time() -start
print(\"find %s in %s seconds\" % (num,end))

结果为：

find 224737 in 0.427901029586792 seconds

Process finished with exit code 0

0.4秒，非常迅速。

无关问题

===============================这里是与主题无关的分割线===============================

初用segment fault感觉还是不太一样，在以前的写博客习惯下，随便试了一些方法，除了tab之外还没有找到特别有趣的特殊格式。特别例如平方号等特殊符号，没能够实验出来。官方是否能出一份文章特殊符号和格式的使用说明呢？

以上问题，非常感谢高阳sunny的迅速回复，祝segment fault越办越出众！

一栏一槽


===============================这里是与上述都无关的分割线===============================

听说一位同学要去人民大学读研，去寒暄了一下：
“你要去人大？”
“恩”
“什么时候去当常委？dog rich, don\'t forget!”
“......”
于是我回到美帝以后，发现又遭到报应性冷空气了。。。

14年时初，拜访康村，和cornell的同学冒着雪天，黄昏时分在康村取景拍下的照片

线性素数筛选（linear sieve for prime number）

问题起源

算法演绎

算法分析

算法演绎

相关算法

无关问题

一栏一槽