我的筛子：求2－100之间的素数
#include <iostream>

using namespace std ;

const int MAX = 100 ;

void main()
{
    int array[MAX+1] ;

    for( int i = 1 ; i <= MAX ; i++  )
    {
        array[i] = 1 ;
    }

    for( i = 2 ; i <= MAX/i ; i++ )
    {
        for( int j = 2 ; j <= MAX/i ; j++ )
        {
            array[i*j] = 0 ;
        }
    }

    for( i = 2 ; i <= MAX ; i ++  )
    {
        if( array[i] == 1 )
        {
            cout << i<<" " ;
        }
    }

}

以上便是著名的sieve of Eratosthenes

for( i = 2 ; i <= MAX/i ; i++ )
    {
        for( int j = 2 ; j <= MAX/i ; j++ )
对不起啊，这里的循环写错了，外存循环应该是
    for( i = 2 ; i <= MAX/2 ; i++ )
    {
        for( int j = 2 ; j <= MAX/i ; j++ )

[quote]我见到的最快的筛选素数的程序是10亿内素数只需1秒（PIV 2.4g)。但它的源程序有几千行。[/quote]
你能找到它的源程序吗？
发给我：zhxd300@163.com

就是这样了呀：
如求20以内的素数： 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

第一步：先把奇数保留，N%2==0，先筛去偶数！
第二步：用找到的第一，二，三，。。。个素数去除后面的数，把能它被整除的数筛去！例如：
首先用2去筛后面的数
如：
     2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
 用2除:2 3 5 6 7 9 11 13 15 17 19 
 用3除:2 3 5 7 11 13 17 19
 。。。。。
 此时，留下的就全是素数了！

附程序如下：
NO.1
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
long N;
typedef struct prime
{
 long data;
 struct prime *next;
}PRI;
 
 PRI *creat_list(PRI *head)
 {
   PRI *po,*nw;
   long i;
   po=head->next;
   nw=(PRI *)malloc(sizeof(PRI));
   nw->data=2;
   nw->next=NULL;
   po->next=nw;
   po=nw;
   for(i=3;i<=N;i+=2)
   {
    nw=(PRI *)malloc(sizeof(PRI));
    nw->data=i;
    nw->next=NULL;
    po->next=nw;
    po=nw;
   }
  return head;
}

PRI *del_data(PRI *head)
{
 long k;
 PRI *s,*e,*m,*pt;
 k=(long)sqrt(N);
 pt=head->next;
 while(pt && pt->data<=k)
 {
  s=pt;
  e=pt->next;
  while(e)
  {
   if(e->data%pt->data==0)
   s->next=e->next;
   e=s->next->next;
   s=s->next;
  }
  pt=pt->next;
 }
  return 0;
} 
 
 
 
 
int main()
{
 PRI *head,*p,*q;
 long num=0;
 printf("Input the number:");
 scanf("%ld",&N);
 p=(PRI *)malloc(sizeof(PRI));
 p->next=NULL;
 head=p;
 head=creat_list(head);
 head=del_data(head);
 
 q=head->next;
 
 
 while(q)
 {
  num++;
  q=q->next;
 }

 printf("\nIn the num of %ld has %ld primes!",N,num);

 return 0;
}

NO.2

[quote你能找到它的源程序吗？
发给我：zhxd300@163.com[/quote]
已发。

璋㈣阿锛

单个素数判断可用Miller-Rabin算法

费马小定理 如果P是一个素数，且0<a<p,则a^(p-1)≡1(mod p)

例如，67是一个素数，则2^66mod 67=1。 
利用费马小定理，对于给定的整数n，可以设计一个素数判定算法。通过计算d=2^(n-1)mod n来判定整数n的素性。当d不等于1时，n肯定不是素数；当d等于1时，n则很可能是素数。但也存在合数n使得2^(n-1)≡1(mod n)。例如，满足此条件的最小合数是n=341。为了提高测试的准确性，我们可以随机地选取整数1费马小定理毕竟只是素数判定的一个必要条件。满足费马小定理条件的整数n未必全是素数。有些合数也满足费马小定理的条件。这些和数被称做Carmichael数，前3个Carmichael数是561,1105,1729。Carmichael数是非常少的。在1~100000000范围内的整数中，只有255个Carmichael数。利用下面的二次探测定理可以对上面的素数判定算法作进一步改进，以避免将Carmichael数当作素数。

二次探测定理 如果p是一个素数，0<x<p,则方程x^2≡1(mod p)的解为x=1,p-1


＃include <iostream.h> 
＃include <time.h> 
＃include <stdlib.h> 

//随机数产生器 
//产生m~n之间的一个随机数 
unsigned long random(unsigned long m,unsigned long n) 
{ 
srand((unsigned long)time(NULL)); 
return (unsigned long)(m+rand()%n); 
} 
//模幂函数 
//返回X^Y mod N 
long PowMod(long x,long y,long n) 
{ 
long s, t, u; 

s=1; t=x; u=y; 
while(u){ 
if(u&1)s=(s*t)%n; 
u>>=1; 
t=(t*t)%n; 
} 
return s; 
} 


//Rabin-Miller素数测试，通过测试返回1，否则返回0。 
//n是待测素数。 
//注意：通过测试并不一定就是素数，非素数通过测试的概率是1/4 

int RabinMillerKnl(unsigned long n) 
{ 
unsigned long b, m, j, v, i; 
//先计算出m、j，使得n-1=m*2^j，其中m是正奇数，j是非负整数 
m=n - 1; 
j=0; 
while(!(m & 1)) 
{ 
++j; 
m>>=1; 
} 
//随机取一个b，2<=b<n-1 
b=random(2,m); 
//计算v=b^m mod n 
v=PowMod(b, m, n); 
//如果v==1，通过测试 
if(v == 1) 
{ 
return 1; 
} 

i=1; 
//如果v=n-1，通过测试 
while(v != n - 1) 
{ 
//如果i==l，非素数，结束 
if(i == j) 
{ 
return 0; 
} 
//v=v^2 mod n，i=i+1 
v=PowMod(v, 2, n); 
i++; 
} 
return 1; 
} 
int main() 
{ 
unsigned long p; 
int count=0; 
cout<<"请输入一个数字"<<endl; 
cin>>p; 
for(int temp=0; temp < 5; temp++) 
{ 
if(RabinMillerKnl(p)) 
{ 
count++; 
} 
else 
break; 

} 

if(count==5) 
cout<<"一共通过5次测试，是素数！"<<endl; 
else 
cout<<"不是素数"<<endl; 
return 0; 
}

用pascal的解法：
program prime;
   const q=100000;
 var
   b,c,i,j:integer;
  a:array[1..q] of integer;
  begin
   for i:=1 to q do a[i]:=1;
   write('please put the maximum value');writeln;read(b);
   for i:=b+1 to q do a[i]:=0;
   a[1]:=2;i:=2;j:=1;
   while i<=b do
   begin
      while a[i]=1 do
       begin
        while i+j*i<=b do begin a[i+j*i]:=0; inc(j); end;
        inc(i);
        end;
        inc(i);
      end;
    for j:=1 to b do if a[j]=1 then write(j,'  ');readln;readln;
    end.