简介

步骤

c语言实现

pascal实现

C++实现(基本算法 高效利用cache的算法)

简介

埃拉托色尼选筛法(the Sieve of Eratosthenes)简称埃氏筛法，是古希腊数学家埃拉托色尼(Eratosthenes 274B.C.～194B.C.)提出的一种筛选法。 是针对自然数列中的自然数而实施的，用于求一定范围内的质数，它的容斥原理之完备性条件是p=H~。

步骤

（1）先把1删除（现今数学界1既不是质数也不是合数）

（2）读取队列中当前最小的数2，然后把2的倍数删去

（3）读取队列中当前最小的数3，然后把3的倍数删去

（4）读取队列中当前最小的数5，然后把5的倍数删去

（5）如上所述直到需求的范围内所有的数均删除或读取

注：此处的队列并非数据结构队列，如需保留运算结果，处于存储空间的充分利用以及大量删除操作的实施，建议采用链表的数据结构。

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;

for(p = a; p < a+SIZE; ++p) {

while(i < SIZE) { /*找到下一个质数*/

if(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("\");

return 0;

}

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;

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;

}

}