Phương pháp sàng số nguyên tố Sieve of Eratosthenes là một trong những phương pháp hiệu quả nhất trong việc tìm ra các số nguyên tố nhỏ hơn n (n <= 10.000.000).

Ví dụ: Tìm tất cả số nguyên tố nhỏ hơn 50

Bước 1: Xét 2 là số nguyên tố, ta sẽ loại bỏ tất cả bội số của 2 mà lớn hơn hoặc bằng bình phương của 2

Bước 2: Xét 3 là số nguyên tố, ta sẽ loại bỏ tất cả bội số của 3 mà lớn hơn hoặc bằng bình phương của 3

Bước 3: Xét 5 là số nguyên tố, ta sẽ loại bỏ tất cả bội số của 5 mà lớn hơn hoặc bằng bình phương của 5

Ta cứ xét tiếp như vậy, cuối cùng sẽ được:

Tất cả các số còn lại sẽ là số nguyên tố: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.

#include <bits/stdc++.h>

using namespace std;

vector<int> primes(10000005,0);

void SangSNT(){
    int n = 1000;
    for (int i=2; i*i<=n; i++){
        if (primes[i]==0) {
            for (int j=i*i; j<=n; j+=i){
                primes[j] = 1;
            }
        }
    }

    // In tat ca so nguyen to
    for (int i = 2; i <= n; i++)
        if (primes[i]==0) cout << i << " ";
}

int main()
{
    SangSNT();
    return 0;
}