素数线性筛

/* 素数线性筛 */
#include <cstdio>
#include <cstring>

const int maxn = 1000;
bool flag[maxn+1];
int prime[maxn + 1];
int priNum;

int main()
{
    priNum = 0; //初始化为0个素数
    memset(flag, 1, sizeof flag); //初始全部标记为素数

    for (int i = 2; i <= maxn; ++i){
        //筛去所有最大因素是i的合数(i*一个素数(该素数不大于i的小素因子的))
        if (flag[i]){
            prime[priNum++] = i; //i是素数记录下来
        }
        for (int j = 0; j < priNum && prime[j] * i <= maxn; ++j){
            //筛去合数
            flag[i*prime[j]] = 0;
            if (i%prime[j] == 0){
                break; //遇到最小素因子，结束
            }
        }
    }
    int kase = 0;
    for (int i = 2; i < maxn; ++i){
        if (flag[i]){
            printf("%d ", i);
            ++kase;
            if (kase % 5 == 0){
                printf("\n");
            }
        }
    }

    for (int i = 0; i < priNum; ++i){
        printf("%d ", prime[i]);
        if ((i + 1) % 5 == 0){
            printf("\n");
        }
    }


    return 0;
}