求素数表

#include<cstdio>
bool vis[100010] = { 0 };
int prime[100010] = { 0 };

int isprime(int n) {
    /*
    欧拉筛选素数。
    筛选n（包括n）以内的素数，返回素数个数。
    时间复杂度：O(n)。
    */
    int cnt = 0;
    for (int i = 2;i <= n;++i) {
        if (!vis[i]) {
            prime[cnt++] = i;
        }
        for (int j = 0;j < cnt&&i*prime[j] <= n;++j) {
            vis[i*prime[j]] = 1;
            if (i%prime[j] == 0)break;
        }
    }
    return cnt;
}

int main(){
    int N,cnt=0;
    scanf("%d",&N);
    isprime(N);
    for(int i=0;i<=N;++i){
        if(vis[i]!=0){
            printf("%d ",i);
            cnt++;
        }
        if(cnt==5){
            cnt=0;
            printf("\n");
        }

    }
    return 0;
}