这篇文章主要为大家详细介绍了python素数筛选法的相关资料，具有一定的参考价值，感兴趣的小伙伴们可以参考一下
原理：
素数，指在一个大于1的自然数中，除了1和此整数自身外，不能被其他自然数整除的数。在加密应用中起重要的位置，比如广为人知的RSA算法中，就是基于大整数的因式分解难题，寻找两个超大的素数然后相乘作为密钥的。一个比较常见的求素数的办法是埃拉托斯特尼筛法(the Sieve of Eratosthenes) ，说简单一点就是画表格，然后删表格，如图所示：
从2开始依次往后面数，如果当前数字一个素数，那么就将所有其倍数的数从表中删除或者标记，然后最终得到所有的素数。
有一个优化：
标记2和3的倍数的时候，6被标记了两次。所以从i的平方开始标记，减少很多时间。
比如3的倍数从9开始标记，而不是6，并且每次加6。
除了2以外，所有素数都是奇数。奇数的平方还是奇数，如果再加上奇数就变成了偶数一定不会是素数，所以加偶数(2倍素数)。
预先处理了所有偶数。
注意：1既不是素数也不是合数，这里没有处理1。
#! prime.py import time def primes(n): P = [] f = [] for i in range(n+1): if i > 2 and i%2 == 0: f.append(1) else: f.append(0) i = 3 while i*i <= n: if f[i] == 0: j = i*i while j 2 and n%2 == 0: return 0 i = 3 while i*i <= n: if n%i == 0: return 0 i += 2 return 1 def primeCnt(n): cnt = 0 for i in range(2,n): if isPrime(i): cnt += 1 return cnt if __name__ == '__main__': start = time.clock() n = 10000000 P = primes(n); print("There are %d primes less than %d"%(len(P),n)) #for i in range(10): # print(P[i]) print("Time: %f"%(time.clock()-start)) #for n in range(2,100000): # if isPrime(n): # print("%d is prime"%n) #print("%d is "%n + ("<mark style="color:transparent">来源gaodaimacom搞#代%码网</mark>prime" if isPrime(n) else "not prime")) start = time.clock() n = 1000000 print("There are %d primes less than %d"%(primeCnt(n),n)) print("Time: %f"%(time.clock()-start)
用素数筛选法求1千万以内的素数用了5.767s，
普通素数判断法求1百万以内的素数用了9.642s，
用C++素数筛选法求1亿以内的素数用了0.948s，
用C++普通素数判断法求1千万以内的素数用了3.965s，
可见解释语言确实比编译语言慢很多。
附C++程序，用了位压缩优化空间
#include #include #include using namespace std; #define N 100000001 unsigned f[(N>>5)+5]; int p[5761456],m; void init() { int i,j; for(i=4;i>5]|=1<<(i&0x1F); p[m++]=2; for(i=3;i*i>5]&(1<<(i&0x1F)))) { p[m++]=i; for(j=i*i;j>5]|=1<<(j&0x1F); } for(;i>5]&(1<<(i&0x1F)))) p[m++]=i; } int is_prime(int n) { int i; for(i=0;p[i]*p[i]2 && n%2==0) return 0; int i=3; while(i*i<=n) { if(n%i==0) return 0; i+=2; } return 1; } int main() { int n=0,i; clock_t st=clock(); init(); /*for(i=2;i<10000000;i++) if(isPrime(i)) n++;*/ printf("%d %dms\n",m,clock()-st); /*while(~scanf("%d",&n),n) { i=lower_bound(p,p+m,n+1)-p; printf("%d\n",i); }*/ return 0; }
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持gaodaima搞代码网。
以上就是python素数筛选法浅析的详细内容，更多请关注gaodaima搞代码网其它相关文章！
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：python素数筛选法浅析
转载请注明原文链接：python素数筛选法浅析
