c++

C++实现素数筛选法

小樊
84
2024-08-23 15:22:28
栏目: 编程语言

#include <iostream>
#include <vector>

using namespace std;

void sieveOfEratosthenes(int n) {
    vector<bool> isPrime(n+1, true);
    
    for (int p = 2; p*p <= n; p++) {
        if (isPrime[p]) {
            for (int i = p*p; i <= n; i += p) {
                isPrime[i] = false;
            }
        }
    }
    
    for (int p = 2; p <= n; p++) {
        if (isPrime[p]) {
            cout << p << " ";
        }
    }
}

int main() {
    int n;
    cout << "Enter a number: ";
    cin >> n;
    
    cout << "Prime numbers up to " << n << " are: ";
    sieveOfEratosthenes(n);
    
    return 0;
}

此代码实现了素数筛选法,输出小于等于给定数n的所有素数。

0
看了该问题的人还看了