内容简介：这篇文章主要为大家详细介绍了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 <= n:
f[j] = 1
j += i+i
i += 2
P.append(2)
for i in range(3,n,2):
if f[i] == 0:
P.append(i)
return P
def isPrime(n):
if n > 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 + ("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 <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 100000001
unsigned f[(N>>5)+5];
int p[5761456],m;
void init()
{
int i,j;
for(i=4;i<N;i+=2)
f[i>>5]|=1<<(i&0x1F);
p[m++]=2;
for(i=3;i*i<N;i+=2)
if(!(f[i>>5]&(1<<(i&0x1F))))
{
p[m++]=i;
for(j=i*i;j<N;j+=i+i)
f[j>>5]|=1<<(j&0x1F);
}
for(;i<N;i+=2)
if(!(f[i>>5]&(1<<(i&0x1F))))
p[m++]=i;
}
int is_prime(int n)
{
int i;
for(i=0;p[i]*p[i]<=n;i++)
if(n%p[i]==0)
return 0;
return 1;
}
int isPrime(int n)
{
if(n>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;
}
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Iterative Methods for Sparse Linear Systems, Second Edition
Yousef Saad / Society for Industrial and Applied Mathematics / 2003-04-30 / USD 102.00
Tremendous progress has been made in the scientific and engineering disciplines regarding the use of iterative methods for linear systems. The size and complexity of linear and nonlinear systems arisi......一起来看看 《Iterative Methods for Sparse Linear Systems, Second Edition》 这本书的介绍吧!
