快捷導(dǎo)航

python素?cái)?shù)篩選法淺析

更新時(shí)間：2018年03月19日 14:46:27 作者：power721

這篇文章主要為大家詳細(xì)介紹了python素?cái)?shù)篩選法的相關(guān)資料，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

原理：

　　素?cái)?shù)，指在一個(gè)大于1的自然數(shù)中，除了1和此整數(shù)自身外，不能被其他自然數(shù)整除的數(shù)。在加密應(yīng)用中起重要的位置，比如廣為人知的RSA算法中，就是基于大整數(shù)的因式分解難題，尋找兩個(gè)超大的素?cái)?shù)然后相乘作為密鑰的。一個(gè)比較常見的求素?cái)?shù)的辦法是埃拉托斯特尼篩法(the Sieve of Eratosthenes) ，說(shuō)簡(jiǎn)單一點(diǎn)就是畫表格，然后刪表格，如圖所示：

　　從2開始依次往后面數(shù)，如果當(dāng)前數(shù)字一個(gè)素?cái)?shù)，那么就將所有其倍數(shù)的數(shù)從表中刪除或者標(biāo)記，然后最終得到所有的素?cái)?shù)。

有一個(gè)優(yōu)化：

標(biāo)記2和3的倍數(shù)的時(shí)候，6被標(biāo)記了兩次。所以從i的平方開始標(biāo)記，減少很多時(shí)間。

比如3的倍數(shù)從9開始標(biāo)記，而不是6，并且每次加6。

除了2以外，所有素?cái)?shù)都是奇數(shù)。奇數(shù)的平方還是奇數(shù)，如果再加上奇數(shù)就變成了偶數(shù)一定不會(huì)是素?cái)?shù)，所以加偶數(shù)(2倍素?cái)?shù))。

預(yù)先處理了所有偶數(shù)。

注意：1既不是素?cái)?shù)也不是合數(shù)，這里沒(méi)有處理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)

用素?cái)?shù)篩選法求1千萬(wàn)以內(nèi)的素?cái)?shù)用了5.767s，

普通素?cái)?shù)判斷法求1百萬(wàn)以內(nèi)的素?cái)?shù)用了9.642s，

用C++素?cái)?shù)篩選法求1億以內(nèi)的素?cái)?shù)用了0.948s，

用C++普通素?cái)?shù)判斷法求1千萬(wàn)以內(nèi)的素?cái)?shù)用了3.965s，

可見解釋語(yǔ)言確實(shí)比編譯語(yǔ)言慢很多。

附C++程序，用了位壓縮優(yōu)化空間

#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; 
}

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: