筛法求素数表

#include <cstdio>
#include <cmath>
#include <cstring>

using namespace std;

const int N = 10000;
int vis[N];
int prime[N];

void primeTable()
{
        //int m = static_cast<int>(sqrt(0.5 + N));
        int c = 0;
        memset(vis, 0, sizeof(vis));

        for(int i = 2; i < N; i++)
        {
                if(!vis[i])
                {
                        prime[c++] = i;
                }
                for(int j = i * i; j < N; j+=i)
                {
                        vis[j] = 1;
                }
        }

        printf("table size : %d\n", c);
        /*
        for(int i = 0; i < c; i++)
        {
                if(i % 20 == 0)
                {
                        printf("\n");
                }
                printf("%d ", prime[i]);
        }

        printf("\n");
        */
}

int main()
{
        primeTable();
}

输出结果：

table size : 1229