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) 

本文名称：python素数筛选法浅析-创新互联
路径分享：http://bjjierui.cn/article/diepii.html