题解 | #筛选法求素数#

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[n - 1];
    for (int i = 0; i < n - 1; ++i)
    {
        a[i] = i + 2;
    }
    for (int i = 2; i < n; ++i)
    {
        for (int j = i - 1; j < n - 1; ++j)
        {
            if (a[j] != 0 && a[j] % i == 0)
                a[j] = 0;
        }
    }
    int cnt = 0;
    for (int j = 0; j < n - 1; ++j)
    {
        if (a[j] != 0)
            cout << a[j] << " ";
        else
            cnt++;
    }
    cout << endl;
    cout << cnt;
}
// 64 位输出请用 printf("%lld")

按题目意思来就行，注意筛数法题目的要求：数组中2之后的所有能被2整除的数清0，再将3之后的所有能被3整除的数清0，要在之后清零！