基本介紹
- 中文名：埃拉托色尼篩選法
- 外文名：the Sieve of Eratosthenes
- 簡稱：埃氏篩法
- 提出：古希臘數學家埃拉托色尼
埃氏篩法步驟,c語言,C++,java,pascal,python,
埃氏篩法步驟
（1）先把1刪除（現今數學界1既不是質數也不是合數）
（2）讀取佇列中當前最小的數2，然後把2的倍數刪去
（3）讀取佇列中當前最小的數3，然後把3的倍數刪去
（4）讀取佇列中當前最小的數5，然後把5的倍數刪去
（5）讀取佇列中當前最小的數7，然後把7的倍數刪去
（6）如上所述直到需求的範圍內所有的數均刪除或讀取
註：此處的佇列並非數據結構佇列，如需保留運算結果，處於存儲空間的充分利用以及大量刪除操作的實施，建議採用鍊表的數據結構。
c語言
以下是一個較易理解的算法
#include <stdio.h>
#define TRUE 1
#define FALSE 0
#define SIZE 10000
int main()
{
int i; /*i表示整數和對應的下標*/
int j; /*j表示正要處理的質數j之前的已處理j之後的未處理*/
int k; /*k表示正在處理的j的倍數從2開始到j*k<SIZE*/
int a[SIZE]; /*下標表示整數內容判斷是否為質數*/
int *p; /*控制循環*/
for(p = a; p < a+SIZE; ++p) { /*初始化數組全是TRUE*/
*p = TRUE;
}
a[0] = a[1] = FALSE; /*設定前面兩個不是質數的數的狀態為FALSE*/
i = 2;
while(i < SIZE) { /*找到下一個質數*/
while(a[i++] == TRUE) {
j = i-1;
break;
}
for(k = 2; j*k < SIZE && i < SIZE; ++k) { /*處理質數的倍數*/
a[j*k] = FALSE;
}
}
for(p = a; p < a+SIZE; ++p) { /*列印出質數*/
if(*p == TRUE) {
printf("%8d", p-a);
}
}
printf("\n");
return 0;
}
C++
基本算法
#include <iostream>using namespace std;void FilterPrime(int n){bool* isPrimes = new bool[n+1];for(int i=2;i<=n;++i)isPrimes[i] = true;isPrimes[2] = true;for(int j=2;j<=n;++j)if(isPrimes[j]==true)for(int m=2;j*m<=n;++m)isPrimes[j*m] = false;for(int k=2;k<=n;++k)if(isPrimes[k]==true)cout<<k<<"是素數"<<endl;delete [] isPrimes;}int main(){int num;cin>>num;FilterPrime(num);system("pause");return 0;}高效利用cache的算法
其中包含偽代碼
long CacheFriendlySieve(long n){
long count=0;
long m=(long)sqrt((double)n);
bool* composite=new bool[n+1];
memset(composite,0,n);
long* factor=new long[m];
long* striker=new long[m];
longn_factor=0;
for(long i=2;i<m;++i)
if(!composite[i]){
++count;
striker[n_factor]=Strike(composite,2*i;i,m);
factor[n_factor++]=i;
}
//將篩劃分成大小為sqrt(n)的視窗
for(long window=m+1;window<=n;window+=m){
long limit=min(window+m-1,n);
for(long k=0;k<n_factor;++k){
//Strike遍歷視窗大小為sqrt(n)的部分數組
Striker[k]=Strike();
for(long i=window;i<limit;++i)
if(!composite[i])
++count;
}
delete[] striker;
delete[] factor;
delete[] composite;
return count;
}
}
java
//Scieve.java
import java.util.*;
/**
This program runs the sieve of Eratprstjemes benchmark.
It computes all primes up to 2,000,000
*/
public class Sieve{
public static void main(String[] args){
int n = 2000000;
long start = System.currentTimeMillis();
BitSet b = new BitSet(n+1);
int count = 0;
int i;
for(i = 2; i<=n; i++)
b.set(i);
i = 2;
while(i*i<=n){/*sqrt(n),思考為什麼是到這個數後面的數就都確定了,在往上加的話,相對於i的另一個數就是比i小的數,計算重複*/
if(b.get(i)){//如果該位是質數
count++;
int k=i*i;
while(k<=n){
b.clear(k);
k+=i;//k是i的倍數,將第k位移除
}
}
i++;
}
while(i<=n){//計算sqrt(n)後面的數
if(b.get(i))
count++;
i++;
}
long end = System.currentTimeMillis();
System.out.println(count + "primes");
System.out.println((end - start) + "milliseconds");
}
int n = 2000000;
long start = System.currentTimeMillis();
BitSet b = new BitSet(n+1);
int count = 0;
int i;
for(i = 2; i<=n; i++)
b.set(i);
i = 2;
while(i*i<=n){/*sqrt(n),思考為什麼是到這個數後面的數就都確定了,在往上加的話,相對於i的另一個數就是比i小的數,計算重複*/
if(b.get(i)){//如果該位是質數
count++;
int k=i*i;
while(k<=n){
b.clear(k);
k+=i;//k是i的倍數,將第k位移除
}
}
i++;
}
while(i<=n){//計算sqrt(n)後面的數
if(b.get(i))
count++;
i++;
}
long end = System.currentTimeMillis();
System.out.println(count + "primes");
System.out.println((end - start) + "milliseconds");
}
}
pascal
maxfactor:=trunc(sqrt(maxp));//篩法求素數
fillchar(sieve,sizeof(sieve),true);
for i:=2 to maxfactor do
if sieve[i] then
begin
newp:=i+i;
while newp<=maxp do
begin
sieve[newp]:=false;
newp:=newp+i;//每次取出這個數的倍數
end;
end;
python
def _int_iter():#生成器生成從3開始的無限奇數序列 n = 1 while True: n = n + 2 yield ndef _not_divisible(n):#定義篩選函式 return lambda x:x % n > 0def primes(): yield 2 #先返回一個2 it = _int_iter() # 初始序列 while True: n = next(it) # 返回序列的第一個數 yield n it = filter(_not_divisible(n), it) # 構造新序列for n in primes():#構造循環條件，使之可以輸出任何範圍的素數序列 if n < 1000: print(n) else: break
