基本思想

C语言实现

pascal实现:

C++实现:

python 实现:

基本思想

用筛法求素数的基本思想是：把从1开始的、某一范围内的正整数从小到大顺序排列， 1不是素数，首先把它筛掉。剩下的数中选择最小的数是素数，然后去掉它的倍数。依次类推，直到筛子为空时结束。如有：

1 2 3 4 5 6 7 8 9 10

11 12 13 14 15 16 17 18 19 20

21 22 23 24 25 26 27 28 29 30

1不是素数，去掉。剩下的数中2最小，是素数，去掉2的倍数，余下的数是：

3 5 7 9 11 13 15 17 19 21 23 25 27 29

剩下的数中3最小，是素数，去掉3的倍数，如此下去直到所有的数都被筛完，求出的素数为：

2 3 5 7 11 13 17 19 23 29

C语言实现

#define RANGE 200

#include <stdio.h>

void main(void)

{

int sieve[RANGE + 1];

int i,j,count;

for(i = 0;i <= RANGE;i ++)

sieve[i] = 1;//初始化

sieve[0] = sieve[1] = 0;//0和1不是素数

count = 0;

for(i = 2;i <= RANGE;i ++)

if(sieve[i] == 1)//i是素数

{

printf("%5d",i);//输出素数

count ++;

if(count % 8 == 0)//每行输出8个值

printf("\");

for(j = i;j <= RANGE; j += i)

sieve[j] = 0;//筛去i的倍数

}

printf("\");

}

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;

}

python 实现:

#!/usr/bin/env python

#-*- coding:utf-8 -*-

alist = [2, 3]

def isornot(anum, a):

for i in a:

if anum % i == 0:

return False

a.append(anum)

return True

for e in range(2,100000):

isornot(e, alist)

print alist