C++ 筛选法求素数 - 0 到 M 的素数

#include #include using namespace std;

void sieve(int M) { vector isPrime(M + 1, true); isPrime[0] = isPrime[1] = false;

for (int i = 2; i * i <= M; i++) {
    if (isPrime[i]) {
        for (int j = i * i; j <= M; j += i) {
            isPrime[j] = false;
        }
    }
}

for (int i = 2; i <= M; i++) {
    if (isPrime[i]) {
        cout << i << endl;
    }
}

}

int main() { int M; cin >> M;

sieve(M);

return 0;

}