質(zhì)數(shù)(PRime number)又稱素?cái)?shù)，除了1和它本身外，不能整除以其他自然數(shù)，換句話說(shuō)就是該數(shù)除了1和它本身以外不再有其他的因數(shù)；否則稱為合數(shù)。最小的質(zhì)數(shù)是2。
要判斷一個(gè)整數(shù)N是不是質(zhì)數(shù)很簡(jiǎn)單，看它是否能被2到sqrt(N)之間的整數(shù)整除即可。
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
不過(guò)要找出1到N之間的所有質(zhì)數(shù)時(shí)，一個(gè)個(gè)的判定顯然不是一個(gè)好主意。由于合數(shù)可以分解成一系列質(zhì)數(shù)之積，所以1到N之間的合數(shù)都是1到sqrt(N)之間某個(gè)質(zhì)數(shù)的倍數(shù)，排除這些合數(shù)，剩余的即為質(zhì)數(shù)：
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開(kāi)始判斷是否為質(zhì)數(shù)，并排除質(zhì)數(shù)的倍數(shù)，當(dāng)2至i都被判斷后，i+1是否為質(zhì)數(shù)已很明確。
SPOJ Problem 2 Prime Generator 要求找出n至m之間的質(zhì)數(shù)，其中1 <= m <= n <= 1000000000, n-m<=100000。
這種情況下建一個(gè)1000000000長(zhǎng)度的序列就太浪費(fèi)空間了，需要先找出1至sqrt(n)之間的質(zhì)數(shù)，然后將n與m之間這些質(zhì)數(shù)的倍數(shù)排除：
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
新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
