https://ybt.ssoier.cn/problem_show.php?pid=2040

【题目描述】

用筛法求出n(2≤n≤1000)

以内的全部质数。

【输入】

输入n。

【输出】

多行，由小到大的质数。

【输入样例】

10

【输出样例】

2

3

5

7

在数学中，埃拉托色尼筛选法（the Sieve of Eratosthenes）是一种古老的算法，用来找出不超过任何给定整数n的所有质数。

它通过迭代地将每个质数的倍数标记为合数，从第一个质数2开始。一个给定质数的倍数组成一个以这个质数开头的等差数列，差就是这个质数。一旦所有发现的质数的倍数都被标记为合数，其余未标记的数就是质数。

#include <bits/stdc++.h> 
using namespace std;
bool a[1001];
int main(){
    int n;
    cin >> n;
    for (int i=0;i<=n;i++) a[i] = true;
    a[0] = a[1] = false;
    for(int i=2;i<=n;i++){
        if(a[i]){
            for(int j=i*i;j<=n;j+=i){
                a[j] = false;
            }
        }
    }

    for(int i=0;i<=n;i++){
        if(a[i]){
            cout << i << endl;
        }
    }

    return 0;
}