分享今天研究快速素数求解N以内的素数算法

ydwydw

作者：Raffeale/于大伟

质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，不能被其他自然数整除的数。

一般正常人的解法是两次循环，假设求小于N的所有素数。一次用N-1之间的所有数去除，如果能被整除这个数肯定不是素数。否则是素数。

这个解题的基本思路：

一个数是否是素数其实不需要去除所有N-1的数，在一个群里有人提出一种方法，只要处以N/2之间的所有数字就可以。经过仔细思考，我发现有更快的方法。只要除以这个数的平方根+1之间的所有的即可。这是为什么？听我慢慢道来。



鉴定x是否为素数，最常用的做饭是个从2开始除，一直除到x-1.那么每当用X/n 的时候，N的值依次为[2,3,4,5,6,7,8,9......x-1] .当我们使用X除以2的时候，如果不能整除，说明了x肯定不能被 X/(X/2)整除，并且X不能被小于x/2的值整除。其实就是小学的数学思想,

例如： 10/5 =2  和 10/2=5的性质是一样的。

那么推理证明 X每当除以一个数的时候，N的范围都在缩小。例如，X/2 后 n的范围应该是 x/2-1  ,x/3后N的范围应该x/3-1,说到这里应该明白了吧。

?那也就是说只要一个数不可以被X/10之内所有的数整除的话就说明这个数是素数。这个算法比那个人提出的要快N倍。经过测试在1000000中找出所有的素数，使用python花费25秒钟左右。估计pypy会非常快。

def primesqrt(n):

    result = list()

    result.append(2)

    result.append(3)

    for i in xrange(5,n+1,2):

        for j in xrange(2,int(sqrt(i))+2):

        #for j in range(2,(i>>4)+1):

            if i%j == 0:

                break

        else:

            result.append(i)

   

    return result

ydwydw

pypy找出1000000中所有的素数只用了1秒钟，在我的机器上

icymirror

回复 1# ydwydw


    问题是这个算法早就有人说过了啊？
    在我们还上大学的时候，作素数验证时的算法就是：
    用2~ceil(指定数平方根)范围内的所有质数做因子，如果可以整除，就不是素数，反之，是素数。

ssfjhh

如楼上所说，这算法早就有了。但这不影响楼主独立思考出来的喜悦，对吧？

另外，验证一个整数n是不是素数，不需要验证小于等于n^0.5的所有整数，只需要验证小于等于n^0.5的所有素数即可。

ydwydw

我也是闲来没事，自己琢磨出来的！见笑了！