溫馨提示×

C++實(shí)現(xiàn)素?cái)?shù)篩選法

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;
}

此代碼實(shí)現(xiàn)了素?cái)?shù)篩選法，輸出小于等于給定數(shù)n的所有素?cái)?shù)。

0 踩