题解 SP6471 【TDPRIMES - Printing some primes】

　　　吾皇 · 2019-07-08 21:41:09 · 题解

很简单的一种方法，所以时间复杂度好像要高一点，用的是埃拉托色尼提出的筛法。

开一个bool数组p，先赋初值true，p[1]为false,从2开始一直扫到sqrt（10^8），如果x被扫到且x是true即之前没有被扫过，那么除x之外所有x的倍数一定不是质数

代码如下：

#include<bits/stdc++.h>
using namespace std;
bool p[100000001];int n;
int main(){
    memset(p,true,sizeof(p));//先赋初值
    p[1]=false;//1不是一个质数
    for(int i=2;i<=10000;i++)
        if(p[i]) for(int j=2;i*j<=100000001;j++) p[i*j]=false;//见上述所说
    for(int i=1;i<=100000001;i++){
        if(p[i]){//如果i是一个质数
            n++;//n代表质数的序号，因为一开始是0，所以要先加
            if(n%100==1) cout<<i<<endl;//如果n%100的余数是1，代表这个质数是XX01个，那么就要输出
        }
    }
}