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

biaoxiaoduan 发布于2019-07-24 18:07 / 795人阅读

摘要：转载到其他平台前也请通知我。算法分析由于我们每次寻找的素数时，都从开始，逐渐上除，最后到为止，确认是否是素数。接着继续排除其有关合数。在速度上有略微提升，但是它的算法是主动忽略的相关合数，实际意义并不是很大。

偶然发现了这个和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}loglog 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秒，非常迅速。

相关算法

在论坛中提到过一种 Sieve of Atkin 的算法。在速度上有略微提升，但是它的算法是主动忽略2、3、5的相关合数，实际意义并不是很大。有兴趣的同学也可以看一下。

无关问题

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

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

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

一栏一槽

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

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

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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/37604.html

[Leetcode] Count Primes 数素数

摘要：利用这个性质，我们可以建立一个素数数组，从开始将素数的倍数都标注为不是素数。第一轮将等表为非素数，然后遍历到，发现没有被标记为非素数，则将等标记为非素数，一直到为止，再数一遍素数数组中有多少素数。代码将的倍倍倍都标记为非素数 Count Primes Description: Count the number of prime numbers less than a non-nega...

Achilles 2019-08-14 12:28 评论0 收藏0
204. Count Primes

摘要：题目链接思路首先要知道如何判断一个数字是否为素数。具体方法可以看这里其次，如果朴素的判断，那么会因为效率底下而超时。所以在我们每次找到素数的时候，可以把素数的倍数都标记为非素数。这样可以节省轮询的时间。算法复杂度时间空间代码题目链接：Counting Primes 思路：首先要知道如何判断一个数字是否为素数。具体方法可以看这里其次，如果朴素的判断，那么会因为效率底下而超时。所以在我...

王笑朝 2019-07-30 16:58 评论0 收藏0
JavaScript中的算法（附10道面试常见算法题解决方法和思路）

摘要：中的算法附道面试常见算法题解决方法和思路关注每日一道面试题详解面试过程通常从最初的电话面试开始，然后是现场面试，检查编程技能和文化契合度。值得记住的数组方法有和。一个好的解决方案是使用内置的方法。 JavaScript中的算法（附10道面试常见算法题解决方法和思路）关注github每日一道面试题详解 Introduction 面试过程通常从最初的电话面试开始，然后是现场面试，检查编程...

Cruise_Chan 2019-08-26 10:22 评论0 收藏0
欧拉函数(Euler' totient function )

摘要：传送门这个就是主角欧拉函数。在数论中，对正整数，欧拉函数是小于或等于的正整数中与互质的数的数目。欧拉函数实际上是模的同余类所构成的乘法群即环的所有单位元组成的乘法群的阶。欧拉函数(Euler totient function ) Author: Jasper Yang School: Bupt 前言 gamma函数的求导会出现所谓的欧拉函数（phi），在一篇论文中我需要对好几个欧...

lewinlee 2019-07-31 12:23 评论0 收藏0