首页 > 代码库 > 素数筛法--SPOJ Problem 2 Prime Generator
素数筛法--SPOJ Problem 2 Prime Generator
质数(prime number)又称素数，除了1和它本身外，不能整除以其他自然数，换句话说就是该数除了1和它本身以外不再有其他的因数；否则称为合数。最小的质数是2。
要判断一个整数N是不是质数很简单，看它是否能被2到sqrt(N)之间的整数整除即可。
def isPrime(n): if n%2==0: return False for i in xrange(3,int(math.sqrt(n)+1),2): if n%i==0: return False return True
不过要找出1到N之间的所有质数时，一个个的判定显然不是一个好主意。由于合数可以分解成一系列质数之积，所以1到N之间的合数都是1到sqrt(N)之间某个质数的倍数，排除这些合数，剩余的即为质数：
import mathimport timeitdef findPrime(n): a=[True]*(n+1) a[0]=False a[1]=False for i in xrange(2,int(math.sqrt(n)+1)): if a[i]: k=i*i while k<=n: a[k]=False k=k+i if __name__==‘__main__‘: t=timeit.Timer(‘findPrime(2000000)‘,‘from __main__ import findPrime‘) print t.timeit(1)
算法从2开始判断是否为质数，并排除质数的倍数，当2至i都被判断后，i+1是否为质数已很明确。
SPOJ Problem 2 Prime Generator 要求找出n至m之间的质数，其中1 <= m <= n <= 1000000000, n-m<=100000。
这种情况下建一个1000000000长度的序列就太浪费空间了，需要先找出1至sqrt(n)之间的质数，然后将n与m之间这些质数的倍数排除：
import mathdef findPrime(n): a=[True]*(n+1) a[0]=False a[1]=False for i in xrange(2,int(math.sqrt(n)+1)): if a[i]: k=i*i while k<=n: a[k]=False k=k+i for i in xrange(2,n+1): if a[i]: yield idef findPrimeBySeed(n,m): if n==1: n=2 seed=findPrime(int(math.sqrt(m))) alist=[1]*(m-n+1) for prime in seed: if prime<n: k=(prime-n%prime)%prime else: k=2*prime-n while k<=m-n: alist[k]=False k+=prime for i in xrange(m-n+1): if alist[i]: print i+n if __name__==‘__main__‘: line=int(raw_input()) for i in xrange(line): n,m=raw_input().split() findPrimeBySeed(int(n),int(m)) print
素数筛法--SPOJ Problem 2 Prime Generator
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。