一、什么是素数?

素数又称为质数。素数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数。素数在日常中最多的应用就是加密算法,例如RSA加密算法就是基于来实现的。RSA算法会随机生成两个1024位的质数相乘,要破解密码必须对乘积做质因数分解,而1024位的质因数分解是非常困难的。

二、如何快速的算出小于某个数的所有素数?

  从素数的概念上似乎可以很快得出一个算素数的公式,即将一个数循环做除法,从1一直除到它本身,如果中途只有被1和自己整除了这个数便是素数了,这样的计算效率是非常差的,因为他会不停的遍历整个数据范围。我们来试着跑一下它的效率:

#求10万以内的素数
import datetime
start = datetime.datetime.now()
for i in range(2,100000):
    for j in range(2,i):
        if i%j == 0:
            break
    #else:
        #print(i)
stop = datetime.datetime.now()
print(stop-start)

 运行结果: 0:01:04.326679 ,在没有print的情况下竟然用了1分多钟,并且数字越大计算越慢。这样的效率肯定是不被允许的。下面介绍一种最常见的质数算法的原理:

三、埃拉托色尼素数筛选法

埃拉托色尼是一名古希腊的地理学家,他是世界上第一个计算出地球周长的人。埃拉托色尼素数筛选法可以很快速的计算出1到N之间的所有素数。将n开根号,即N^0.5,去掉2到N^0.5中所有素数的倍数,剩下的数便都是素数了。例如求1到25中的素数有哪些,第一步是将25开根号,得到5;第二步将2到5的素数取出来,分别是2、3、5;再将2到25中且是2、3、5的倍数的数去掉,即去掉4、6、8、9、10、12、14、15、16、18、20、21、22、24、25,剩下2、3、5、7、11、13、17、19便是1到25中的所有素数了。

  这里还用到了一个数学知识,即只要小于或等于根号N的数(1除外)不能整除N,则N一定是素数;反过来说就是只要小于或等于根号N的数(1除外)能整除N,则N一定是合数。下面给出证明过程:

假设一个数N是合适,那一定存在一个因数b和一个非1且非自身的因数a,即a*b=N

等式两边同时开根号得出:(a*b)^0.5=a^0.5*b^0.5=N^0.5

可以推出:若N为合数,则a和b中一定有一个大于或等于N^0.5,另一个小于或等于N^0.5

  按照这个结论,就只需计算小于等于N^0.5的数了,这样就大大提高了效率(要注意等于N^0.5的这个边界):

#求10万以内的素数
import datetime
start = datetime.datetime.now()
for i in range(2,100000):
    for j in range(2,int(i**0.5+1)): #边界需要加1
        if i%j == 0:
            break
    #else:
        #print(i)
stop = datetime.datetime.now()
print(stop-start)

运行结果: 0:00:00.428024 。可以说是质的飞跃。

小的优化

  我们也可以将偶数事先就排除在外,然后在进行素数筛选:

#求10万以内的素数
import datetime
start = datetime.datetime.now()
print(2)
for i in range(3,100000,2): #从3开始,跳过偶数
    for j in range(2,int(i**0.5+1)):
        if i%j == 0:
            break
    #else:
        #print(i)
stop = datetime.datetime.now()
print(stop-start)

运行结果: 0:00:00.406024 ,又快了不少。

再次优化:

可以思考:在第一个for循环中已经将跳过了所有的偶数,在 if i%j == 0: 语句中i只有奇数,而在数学中任何奇数除以偶数是一定除不尽的,也就数说当j为偶数时,语句 i%j == 0: 一定是为假的。所以可以将j中的偶数也去掉

#求10万以内的素数
import datetime
start = datetime.datetime.now()
print(2)
for i in range(3,100000,2): #从3开始,跳过偶数
    for j in range(3,int(i**0.5+1),2): #再将j的偶数去掉
        if i%j == 0:
            break
    #else:
        #print(i)
stop = datetime.datetime.now()
print(stop-start)

运行结果: 0:00:00.271016 ,比之前的有快了20毫秒。

再三优化:

用列表的方式进行算法再优化。思路是将每次i循环后如果得到的i是素数则将它累加到一个列表中,并使j在for循环中以这个列表为可迭代对象进行迭代循环,因为列表中所有的元素都是素数,所以j如果迭代到小于等于i^0.5次方时没有能整除的数,说明大于i^0.5次方时也没有能整除的,即此时的i就是素数。这里也用到了一个数学原理:一个数如果能被小于它的素数整除则它一定是一个合数,反之它一定是一个素数。

import datetime
start = datetime.datetime.now()
n = 100000
lst = []
flag = True
#print(2)
for i in range(3,n,2):
    up = i**0.5
    for j in lst:
        if j > up:
            flag = True
            break
        if i % j ==0:
            flag = False
            break
    if flag:
        #print(i)
        lst.append(i)
stop = datetime.datetime.now()
print(stop-start)

运行结果: 0:00:00.177010 ,又快了!

其它优化方案:

  优化方向:

  1.孪生素数对猜想:大于等于5的素数一定与6的倍数相邻。

  2.在奇数中在排除5的倍数。

Categories: Python

1 Comment

Ezekiel · 1月 1, 2019 at 上午10:48

Howdy great blog! Does running a blog like this take a great
deal of work? I’ve very little understanding of computer programming but I had been hoping to
start my own blog in the near future. Anyhow, should you
have any suggestions or tips for new blog owners please share.
I understand this is off subject nevertheless I simply needed
to ask. Thanks!

发表评论

电子邮件地址不会被公开。 必填项已用*标注