Hướng dẫn giải của Thuật toán Sàng nguyên tố

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: Hieu Nguyen

Gợi ý: Sử dụng thuật toán Sàng Eratosthenes

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 0
    nguyendangkhoinguyen  đã bình luận lúc 16, Tháng 6, 2025, 7:30

    include <iostream>

    include <vector>

    using namespace std;

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

    vector<bool> isPrime(n + 1, true); // Khởi tạo tất cả số đều là nguyên tố
isPrime[0] = isPrime[1] = false;   // 0 và 1 không phải số nguyên tố

for (int i = 2; i * i <= n; ++i) {
    if (isPrime[i]) {
        for (int j = i * i; j <= n; j += i)
            isPrime[j] = false; // Đánh dấu các bội số của i không phải số nguyên tố
    }
}

// In các số nguyên tố
for (int i = 2; i <= n; ++i) {
    if (isPrime[i])
        cout << i << " ";
}
cout << endl;

return 0;

    }


  • 0
    Kaishin2402  đã bình luận lúc 4, Tháng 4, 2025, 7:45 ← chỉnh sửa

    .