python求素数的一些算法对比

2019年10月29日 0条评论 601次阅读 0人点赞

素数，又叫质数。是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。否则称为合数。围绕着素数有很多有意思的事情，比如著名的黎曼猜想，哥德巴赫猜想，我国的陈景润和他的“1+2”的故事曾经激励了一代国人发奋学习。素数在加密、量子力学上也有用途。单纯的数学研究素数似乎没什么意义，但是我始终觉得自然的一切都是有关联的，只是以我们的科技水平还没有发现，比如黎曼猜想是爱因斯坦广义相对论和量子力学的部分数学基础。各种事实已经说明了黎曼猜想的正确性，但是黎曼猜想本身却无法得到直接的数学证明。

我在开始学习python的过程中给自己布置过一个题目：

需求：给定一个正整数N，打印出小于N的所有素数以及个数，计算出求素数的时间，以N为50000为例。

1、求余数

（1）n对2~(N-1)进行取余计算

根据素数的定义除了1和它本身以外不再有其他因数的自然数，那么也就是给定一个n，如果用n来分别除以2~(N-1)之间的数，都无法整除，那么就可以确定n是一个质数。

# -*- coding:utf-8 -*-
# 素数计算：基础取余

import time
num=input('请输入一个数：')
begin_time = time.time()
num=int(num)
n=2
k=2
i=0
prime=[]
for n in range(2,num):
    for k in range(2,n):
        if n%k==0:
            break
    else:
        prime.append(n)
        i=i+1
    pass
end_time = time.time()
print(prime)
print('素数个数为：%d' % i)
print('执行时间：%f秒' % (end_time-begin_time))

经过计算，取N=50000，算出来结果如下：

素数个数：5133个

执行时间：27.9秒

（2）改进的取余法

上面算法的时间复杂度有点长，考虑到2以外的所有偶数都能被2整除，都是合数，所以可以先把能整除2的数排除，再计算n除以3~(N-1)之间的间隔为2的数，也就是3，5，7，9……

# -*- coding:utf-8 -*-
# 素数计算：进阶取余

import time
num=input('请输入一个数：')
begin_time = time.time()
num=int(num)
n=2
k=2
i=0
prime=[]
for n in range(2,num):
  if n!=2 and n%2==0:
    continue
  for k in range(3,n,2):
    if n%k==0:
      break
  else:
    prime.append(n)
    i=i+1
  pass
end_time = time.time()
print(prime)
print('素数个数为：%d' % i)
print('执行时间：%f秒' % (end_time-begin_time))

经过计算，取N=50000，算出来结果如下：

素数个数：5133个

执行时间：13.4秒

（3）再次改进的取余法

上面的算法已经优化提升了大概一倍的速度，再进行优化考虑一下是否需要用n来除以3~(N-1)之间的所有奇数？我们知道如果一个自然数有因子，那么一定是成对出现的，比如40，除开它本身1和40，那么还有2和20，4和10，5和8，当已经除了一个比较小的因子时候，另一个因子一定是大于√N的（如√40是6.324…，取整为6，因子小于等于6之后，如果还是不能整除，则肯定大于6的也没有了）于是构造出了一个改良后的算法，先把偶数剔除，再来对3~√(N-1)相邻为2的奇数进行求余数

# -*- coding:utf-8 -*-
# 素数计算3：进阶改良版取余

import time
num=input('请输入一个数:')
begin_time=time.time()
num=int(num)
n=2
k=3
i=0
prime=[]
for n in range(2,num):
    if n!=2 and n%2==0:
        continue
    for k in range(3,int(n**0.5)+1,2):
        if n%k==0:
            break
    else:
        prime.append(n)
        i=i+1
    pass
end_time=time.time()
print(prime)
print('素数个数为：%d' % i)
print('执行时间：%f秒' % (end_time-begin_time))

经过计算，取N=50000，算出来结果如下：

素数个数：5133个

执行时间：0.13秒

2、筛选法

上面的求余算法，感觉已经非常精良，从28秒到0.13秒，将最初的程序效率优化了200多倍。我们已经发现，单独把能被2整除的数，也就是偶数剔除出来，速度就能优化一倍多。那么为什么不可以把能被3，5，7等整除的数都剔除出去呢？这就引申出了筛选法，顾名思义，筛除泥沙，剩下的就是宝石了，他的发明人是公元前250年的希腊人埃拉托斯特尼（埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数）。

（1）筛选法1：

根据埃拉托斯特尼筛法的定义来实现，这里实现是一个定长的求余过程，我们可以先给定一个素数数组作为求余的数组，对它进行取余数，这个数组中的素数越多，计算结果越精确，当然执行效率也就越慢，但是因为素数无计算公式和递归关系，所以不好取范围。仅供参考，这里取100以内的25个数字作为基础数组

# -*- coding:utf-8 -*-
# 素数计算：筛选法1，素数表

import time
num=input('请输入一个数:')
begin_time = time.time()
num=int(num)
PRIMELIST=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
n=2
k=3
primenum=[]
for n in range(2,num):
    if n!=2 and n%2==0:
        continue
    for k in PRIMELIST:
        if n!=k and n%k==0:
            break
    else:
        primenum.append(n)
    pass
end_time = time.time()
print(primenum)
print('素数个数为：%d' % len(primenum))
print('执行时间：%f秒' % (end_time-begin_time))

经过计算，取N=50000，算出来结果如下：

素数个数：5870个 (有误差)

执行时间：0.07秒

（2）筛选法2：

目前看能是非常优良的一个算法了，但是这个算法会以牺牲内存为代价，思路是先申请一个数组，其中默认所有数都是质数，用bool值ture来作为初始值，然后将n的倍数全部都循环设置为False，最后数组中存在的True的部分就是结果了。这种算法非常快，特别是在数据大的时候。

# -*- coding:utf-8 -*-
# 素数计算:筛选法1

import time
num=input('请输入一个数：')
begin_time = time.time()
num=int(num)
prime = []
primenum = []
for i in range(num+1):
    prime.append(True)
for i in range(2,num+1):
    if prime[i]:
        primenum.append(i)
        j = i+i
        while j<= num:
            prime[j] = False
            j=j+i
print(primenum)
end_time=time.time()
print('素数个数为：%d' % len(primenum))
print('执行时间：%f秒' % (end_time-begin_time))

经过计算，取N=50000，算出来结果如下：