python计算孪生素数

给个理由先

python初学者代码

1. 
   
2. 
   
3. import math
   
4. 
   
5. def IsPrime(n):
   
6.         '''calculate a prime'''
   
7.         if n<2:
   
8.                 return False
   
9.         elif n==2 or n==3:
   
10.                 return True
    
11.         elif n%2==0:
    
12.                 return (2, n/2)
    
13. 
    
14.         for i in range(3, 1+n/3, 2):
    
15.             if n%i==0: return (i, n/i)
    
16. 
    
17.         return True
    
18. 
    
19. def Decompose(n):
    
20.         '''decompose/factorization to primes'''
    
21.         if n<=3:
    
22.                 return [n]
    
23. 
    
24.         factors = []
    
25.         rest = n
    
26.         while rest>2:
    
27.                 mark = False
    
28.                 i=2
    
29.                 while i<(1+rest/2):
    
30.                         if rest%i==0:
    
31.                                 factors.append(i)
    
32.                                 rest=rest/i
    
33.                                 mark=True
    
34.                                 break
    
35.                         i+=1
    
36.                 if not mark: break
    
37.         factors.append(rest)
    
38.         factors.sort()
    
39.         return factors
    
40. 
    
41. def PrimeList(bounding=1000):
    
42.         '''all primes in [1~bounding)'''
    
43.         # odds between [3,bounding), cutting all number that can be decomposed!
    
44.         mid = round(math.sqrt(bounding)+1)
    
45.         number = range(3, bounding, 2)
    
46.         for i in number:
    
47.                 if i<>0:
    
48.                         for j in range(i, 1+bounding/i, 2):
    
49.                                 number[(i*j>>1)-1]=0
    
50.                 elif i>mid:
    
51.                         break
    
52.         return [2]+[i for i in number if i<>0]
    
53. 
    
54. def PairPrime(bounding=1000):
    
55.         '''the pair prime in [1~bounding)'''
    
56.         pp=PrimeList(bounding)
    
57.         return [(p[i],p[i+1]) for i in range(len(pp)-1) if p[i]+2==p[i+1]]
    
58. 
    
59. if __name__=='__main__':
    
60.         p=PrimeList(100)
    
61.         print len([i for i in p if IsPrime(i)==True])==len(p), p
    
62.         np=set(range(100))-set(p)
    
63.         print len([i for i in np if IsPrime(i)<>True])==len(np), np
    
64.         pp=PairPrime(100)
    
65.         print len(pp), pp
    

复制代码

给个理由先

IsPrime(n): #判断一个数是否素数，素数返回True，非素数返回第一个分解因数
Decompose(n): #分解质因数
PrimeList(bounding=1000): #计算给定范围的所有素数，使用挖空法，要一次建立一个足够大的数组，所以有内存限制，我的机器上只能到1亿，20秒。
PairPrime(bounding=1000): #计算给定范围的所有孪生素数（距离为2）