筛法求素数

#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);
}