我来说说最基本的筛选法
第一，
剔除2 3 4 5 6 ... ... 的倍数

从i=2开始，第一次剔除2的倍数
不断i++，直到第一个没有被剔除的数
再剔除该数的倍数，
直到循环至问题范围m的平方根+1

证明，假设循环到第n个数，如果该数没有被剔除，那么该数不能是前边所有数的倍数，该数更不可能

是后边数的倍数，该数就是素数。

如果该数是合数即没被剔除，那么该数能分解为两个小于本数的积的形式，而前边剔除的数包含了所有

小于该数的数之间的积，这是矛盾的

第二证明，为什么筛选循环的第一层只循环至问题范围m的平方根+1
因为，对于一个数m，所有大于该数平方根的数的积已经大于该数了，再剔除下去只是多余

第三证明为什么筛选循环的第二层只循环值MAX/i，
因为当j*MAX/i就等与MAX，此时需要标记为错误的数已经到了问题的规模即MAX，没有必要在标记比MAX

大的值不是素数，此外用来标记i*j不是素数的数组只有MAX+1的容量，这样做是向不是自己申请的内存

空间里写数据，是危险的。虽然写在内存的栈区，最后由系统释放


[code=c]
#include <iostream>
#include <cstdlib>
#include <cmath>
using namespace std;
const int MAX=1000;

int main()
{
     int i=0,j=0,n=sqrt(MAX)+1;
     int a[MAX+1]={0};

     for(i=2;i<=n;i++)  //筛选循环
       for(j=2;j<=MAX/i;j++)
           a[j*i]=1;

      
     for(i=2;i<=MAX;i++)
        if(a[i]==0)
        {
             cout.width(7);
          cout<<i<<" ";
        }
     system("pause");
     return 0;
     
}
[/code]

用a[i*j]来标记i*j不是素数，这一个相对来说比较容易想到



再来看看下一个(第二种，稍作了优化)
[code=c]
#include<stdio.h>
#include<math.h>
#define MAX_P  500
int nList[MAX_P] = {0};
void Calc() 
{
    int n,p,t,sq=(int)sqrt(MAX_P*2+1);
    for (n=3;n<=sq;n+=2)
    {
        if (nList[n>>1]) continue;
        for (t=n*n;t<=MAX_P<<1;t+=n<<1) //筛选循环
            nList[t>>1] = 1;
    }
    printf("%5d", 2);
    for (n=t=1;t<MAX_P;++t)
    {
        if (nList[t]) continue;
        printf("%5d", (t<<1)+1);
        if (++n==10)
        {
            printf("\n");
            n=0;
        }
    }
}
int main(void)
{
    Calc();
    getchar();
    return  0;
}[/code]

这个程序的方法是通过排除3 5 7 9 11 ... ...中的素数n的奇数倍，来排除素数的
用数组nList中的第t/2+1的值（取1)来标记t不是素数
1、先说说为什么程序中是奇数倍，

首先我们假设这个算法是正确的
由于素数除了2都是奇数
那么每次送入筛选循环的n值都是奇数，排除t时t的递增表达式可写为
for（int i=0；i<MAX_P/2;i++）
    t=n*（n+2i）
n是奇数n+2i也是奇数


2、然后再来说说为什么3 5 7 9 11 ... ...中的素数n的奇数倍数要从n开始

就是说从1开始和从n开始的效果是一样，
或者说n以前的奇数乘n都可以等于n以前（比n小的）素数的更大奇数倍
由于n是奇数，可以设n以前（比n小的）的奇数为n-2i;比n大的奇数为n+2j
那么我们的任务就是，证明n*（n-2i）可以等于m*（n+2j）
（m为小于n的素数，i、j都是正整数）
即n（n-m）=2mj+2ni
这有变成证明n-m是偶数，这是显然的，两个奇数之差必然是偶数


3、最后我们来证名这个算法是正确的，即证明筛选循环剔除了所有的非素数
余下的证明及另外一种算法的证明请点击下面的链接
[url=http://blog.163.com/tr0217@126/blog/edit/]素数筛选[/url]