* Sàng nguyên tố Eratosthenes (Sieve of Eratosthenes)

Hướng tiếp cận Ban đầu, ta cho tất cả các số từ 2 đến n vào sàng và đánh dấu tất cả các số. (Các số không được đánh dấu sau cùng sẽ bị loại khỏi sàng). Duyệt lần lượt các số từ 2 đến n. Nếu số đang xét:

Đã được đánh dấu

⇒ số nguyên tố: ta bỏ đánh dấu tất cả các bội (khác chính nó) của số nguyên tố này để loại các bội ấy ra khỏi sàng.

Không được đánh dấu

⇒ hợp số: ta bỏ qua số này. Sau khi duyệt xong, các số còn lại trong sàng, hay nói cách khác các số được đánh dấu là số nguyên tố.

Ta có thể hiểu như hình dưới đây:

Code C++ minh họa

const int maxn = 1000000 + 5; //10^6 + 5
bool is_prime[maxn]; // mảng bool khởi tạo với các giá trị false  
void sieve(int n){
    // Đánh dấu các số từ 2 đến n đều là số nguyên tố
    for (int i = 2; i <= n; i++)
        is_prime[i] = true;
    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) {
            for (int j = i * 2; j <= n; j += i)
            // Bỏ đánh dấu tất cả các số không phải số nguyên tố
                is_prime[j] = false;
        }
    }
}

Độ phức tạp thời gian là O(n*(1/2+1/3+...+1/p) với p là số nguyên tố <= n.

Độ phức tạp thời gian là O(n log log n)

Đô phức tạp không gian là O(n)

Dựa vào Nhận xét trên, ta có cải tiến như sau:

CODE MẪU :

const int maxn = 1000000 + 5; //10^6 + 5
bool is_prime[maxn];
void Eratosthenes(int n){
    for (int i = 2; i <= n; i++)
        is_prime[i] = true;
    for (int i = 2; i * i <= n; i++) {
        if (is_prime[i]) {
            // j sẽ bắt đầu chạy từ i * i
            for (int j = i * i; j <= n; j += i)
                is_prime[j] = false;
        }
    }
}

Độ phức tạp thời gian vẫn vậy.Tuy nhiên, số phép tính đã giảm đi đáng kể.

>> link hướng dẫn chi tiết về sàng nguyên tố