筛法求素数

　　筛法求素数的原理是这样的，先找到第一个素数，然后将第一个素数的倍数都去掉，然后找到第二个素数，然后将第二个素数的倍数都去掉。

筛法求素数可以很容易求得小于n的所有素数。

如果要求第n个素数，那么就要用素数定理，求得第n个素数所在的范围，然后再用筛法。

#include <stdio.h>
#include <string.h>
#include <math.h>
const int N = 10000;
bool vis[N];
/*
偶数都不是素数，所以偶数的倍数没必要去掉
*/
void getPrimeTable(int n)
{
    int i,j;
    int t = sqrt(n);
    for(i=3; i<=t; i+=2)//从3开始，将素数的倍数去掉
    {
        if(!vis[i])//!vis表示为素数
        for(j=i*i;j<=n; j+=2*i)//将i的i倍开始标记为非素数，因为偶数不用标记，所以j+=2*i，即让j为奇数
            vis[j] = true;
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    getPrimeTable(n);
    printf("%d",2);
    for(int i=3; i<=n; i+=2)
        if(!vis[i])
            printf(" %d",i);
}