Sàng nguyên tố Eratosthenes và kiểm tra số nguyên tố: code C++, Python

Phần 1: Kiểm tra một số nguyên tố đơn lẻ trong O(√n)

Số nguyên tố (prime number) là số nguyên dương lớn hơn 1 và chỉ có đúng hai ước nguyên dương là 1 và chính nó (ví dụ: 2, 3, 5, 7, 11, 13...). Số 0 và 1 không phải là số nguyên tố; số lớn hơn 1 mà không nguyên tố được gọi là hợp số (composite number).

Nếu một số n là hợp số, nó có thể viết dưới dạng tích của hai ước n = a × b với 1 < a ≤ b < n. Khi đó chắc chắn ước nhỏ hơn a phải thỏa mãn a × a ≤ a × b = n, tức a ≤ √n.

Vì vậy, để kiểm tra n có phải số nguyên tố không, bạn không bao giờ cần thử chia tới n - 1, mà chỉ cần thử các số i từ 2 tới khi i * i <= n:

• Nếu gặp bất kỳ số i nào mà n % i == 0 → kết luận ngay n là hợp số (false).
• Nếu đi hết vòng lặp mà không chia hết cho số nào → n chắc chắn là số nguyên tố (true).

Với n = 10¹², vòng lặp i * i <= n chỉ chạy tối đa 10⁶ bước (mất vài mili-giây). Tuy nhiên, nếu đề bài hỏi: "Đếm xem từ 1 đến 1.000.000 có bao nhiêu số nguyên tố" hoặc cho q = 100.000 truy vấn kiểm tra nguyên tố, việc gọi hàm O(√n) lặp đi lặp lại sẽ mất khoảng n√n bước và bắt đầu chậm. Đó là lúc ta cần Sàng nguyên tố Eratosthenes.

Phần 2: Ý tưởng của Sàng nguyên tố Eratosthenes

Thay vì cầm từng số x đi thử chia xem nó có ước không (phép chia lấy dư % rất tốn thời gian), nhà toán học cổ đại Eratosthenes làm ngược lại: cầm từng số nguyên tố p rồi đi gạch bỏ tất cả các bội số của p (2p, 3p, 4p...) bằng phép cộng nhảy bước!

Quy trình sàng trên đoạn từ 0 đến n diễn ra như sau:

1. Tạo một mảng đánh dấu isPrime[0..n] ban đầu gán tất cả bằng true. Đánh dấu isPrime[0] = isPrime[1] = false.
2. Duyệt p từ 2 đến khi p * p <= n:
   • Nếu isPrime[p] vẫn đang là true (nghĩa là p không phải bội của bất kỳ số nào nhỏ hơn nó → p là số nguyên tố):
   • Ta gạch bỏ các bội của p bắt đầu từ p * p trở đi: p * p, p * p + p, p * p + 2p, ... bằng cách gán isPrime[multiple] = false.
3. Sau khi vòng lặp kết thúc, mọi vị trí i còn giữ isPrime[i] == true chính là toàn bộ các số nguyên tố từ 2 đến n.

Ví dụ từng bước: Sàng các số nguyên tố từ 1 đến 30

Hãy quan sát bảng sàng với n = 30. Vì 5² = 25 ≤ 30 còn 7² = 49 > 30, ta chỉ cần thực hiện gạch bội cho đúng 3 số nguyên tố là p = 2, p = 3 và p = 5:

Code kiểm tra nguyên tố và Sàng Eratosthenes bằng C++ và Python

#include <iostream>
#include <vector>
using namespace std;

// 1. Kiểm tra một số đơn lẻ n có phải số nguyên tố không trong O(sqrt(n))
bool laSoNguyenTo(long long n) {
    if (n < 2) return false;
    for (long long i = 2; i * i <= n; ++i) {
        if (n % i == 0) return false;
    }
    return true;
}

// 2. Sàng nguyên tố Eratosthenes từ 0 đến n trong O(n log log n)
vector<bool> sangEratosthenes(int n) {
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int p = 2; p * p <= n; ++p) {
        if (isPrime[p]) {
            // Bắt đầu gạch từ p * p vì các bội nhỏ hơn đã bị gạch bởi ước nhỏ hơn p
            for (int multiple = p * p; multiple <= n; multiple += p) {
                isPrime[multiple] = false;
            }
        }
    }
    return isPrime;
}

int main() {
    vector<bool> p30 = sangEratosthenes(30);
    for (int i = 2; i <= 30; ++i) {
        if (p30[i]) cout << i << " ";  // 2 3 5 7 11 13 17 19 23 29
    }
    cout << "\n";

    vector<bool> p1m = sangEratosthenes(1000000);
    int dem = 0;
    for (int i = 2; i <= 1000000; ++i) {
        if (p1m[i]) dem++;
    }
    cout << dem << " " << laSoNguyenTo(999999937LL) << "\n";  // 78498 1
    return 0;
}

def la_so_nguyen_to(n):
    """Kiểm tra một số đơn lẻ n có phải số nguyên tố không trong O(sqrt(n))."""
    if n < 2:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True


def sang_eratosthenes(n):
    """Sàng nguyên tố Eratosthenes từ 0 đến n trong O(n log log n)."""
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    p = 2
    while p * p <= n:
        if is_prime[p]:
            # Gạch bội từ p * p với bước nhảy p
            for multiple in range(p * p, n + 1, p):
                is_prime[multiple] = False
        p += 1
    return is_prime


p30 = sang_eratosthenes(30)
print(*(i for i in range(2, 31) if p30[i]))  # 2 3 5 7 11 13 17 19 23 29

p1m = sang_eratosthenes(1000000)
print(sum(p1m), 1 if la_so_nguyen_to(999999937) else 0)  # 78498 1

Độ phức tạp của Sàng Eratosthenes là bao nhiêu?

Với mỗi số nguyên tố p, vòng lặp trong chạy n / p bước. Tổng số bước của toàn bộ thuật toán là: n / 2 + n / 3 + n / 5 + n / 7 + n / 11 + ...

Theo định lý Mertens trong lý thuyết số, tổng nghịch đảo các số nguyên tố nhỏ hơn hoặc bằng n là 1/2 + 1/3 + 1/5 + ... ≈ ln(ln n). Do đó:

• Thời gian: O(n log log n). Với n = 10⁷, log₂(log₂(10⁷)) ≈ 4.5, nghĩa là trung bình mỗi số từ 1 đến n chỉ tốn khoảng 4 phép gán — nhanh gần như một vòng lặp đơn O(n).
• Bộ nhớ: O(n) cho mảng đánh dấu isPrime.

Mở rộng cực mạnh: Phân tích thừa số nguyên tố trong O(log x) bằng mảng SPF

Một ứng dụng rất hay gặp trong đề thi là cần phân tích hàng trăm nghìn số x (x ≤ 10⁶) ra thừa số nguyên tố. Nếu mỗi số bạn lại chạy vòng lặp O(√x) thì với 10⁵ truy vấn sẽ mất khoảng 10⁸ phép chia.

Thay vì chỉ lưu true / false trong bảng sàng, ta tạo mảng spf[i] (Smallest Prime Factor) lưu ước nguyên tố nhỏ nhất của số i:

• Ban đầu gán spf[i] = i.
• Trong lúc sàng, khi số nguyên tố p đi qua bội m, nếu spf[m] vẫn đang bằng m thì ta gán spf[m] = p.
• Khi cần phân tích một số x bất kỳ, ta chỉ việc lấy spf[x] làm thừa số nguyên tố đầu tiên, rồi chia x = x / spf[x] lặp lại cho tới khi x == 1. Vì mỗi lần chia x giảm đi ít nhất một nửa, quá trình phân tích chỉ tốn tối đa log₂ x phép chia!

Hãy xem ví dụ từng bước phân tích số x = 84 chỉ bằng cách tra bảng spf (không cần thử chia cho bất kỳ số nào):

Kết quả phân tích 84 = 2² × 3¹ × 7¹ tìm được sau đúng 4 bước tra mảng! Từ danh sách các thừa số nguyên tố này (p₁^k₁ × p₂^k₂ × ...), bạn còn tính được ngay:

• Tổng số ước nguyên dương của x: d(x) = (k₁ + 1) × (k₂ + 1) × ... (với 84: (2 + 1) × (1 + 1) × (1 + 1) = 12 ước).
• Tổng các ước nguyên dương của x: tích của các cấp số nhân (1 + pᵢ + pᵢ² + ... + pᵢ^kᵢ).

#include <iostream>
#include <vector>
using namespace std;

// Tính ước nguyên tố nhỏ nhất (Smallest Prime Factor — spf) cho mọi số từ 1 đến n
vector<int> taoBangSPF(int n) {
    vector<int> spf(n + 1);
    for (int i = 0; i <= n; ++i) spf[i] = i;
    for (int p = 2; p * p <= n; ++p) {
        if (spf[p] == p) {  // p là số nguyên tố
            for (int m = p * p; m <= n; m += p) {
                if (spf[m] == m) spf[m] = p;
            }
        }
    }
    return spf;
}

// Phân tích x ra thừa số nguyên tố trong O(log x) nhờ bảng spf
vector<int> phanTichThuaSo(int x, const vector<int>& spf) {
    vector<int> thuaSo;
    while (x > 1) {
        thuaSo.push_back(spf[x]);
        x /= spf[x];
    }
    return thuaSo;
}

int main() {
    vector<int> spf = taoBangSPF(1000);
    vector<int> ts = phanTichThuaSo(360, spf);
    for (int i = 0; i < (int)ts.size(); ++i) {
        cout << ts[i] << (i + 1 == (int)ts.size() ? "\n" : " ");  // 2 2 2 3 3 5
    }
    return 0;
}

def tao_bang_spf(n):
    """Tính ước nguyên tố nhỏ nhất (spf) cho mọi số từ 1 đến n."""
    spf = list(range(n + 1))
    p = 2
    while p * p <= n:
        if spf[p] == p:
            for m in range(p * p, n + 1, p):
                if spf[m] == m:
                    spf[m] = p
        p += 1
    return spf


def phan_tich_thua_so(x, spf):
    """Phân tích x ra thừa số nguyên tố trong O(log x)."""
    thua_so = []
    while x > 1:
        thua_so.append(spf[x])
        x //= spf[x]
    return thua_so


spf = tao_bang_spf(1000)
print(*phan_tich_thua_so(360, spf))  # 2 2 2 3 3 5

Một số mẹo tối ưu bộ nhớ và tốc độ cho Sàng Eratosthenes

Khi giới hạn n tiến sát 10⁷ hoặc 10⁸, hai mẹo nhỏ sau đây giúp chương trình của bạn chạy nhanh hơn gấp đôi và tiết kiệm bộ nhớ đáng kể:

1. Chỉ sàng các số lẻ (Tiết kiệm 50% thời gian): Số 2 là số nguyên tố chẵn duy nhất. Bạn có thể xử lý riêng các số chẵn, sau đó chỉ duyệt p = 3, 5, 7... với bước nhảy p += 2. Trong vòng lặp trong, vì p là số lẻ nên p * p là số lẻ và p * p + p là số chẵn (đã bị loại từ đầu); do đó bước nhảy của vòng trong có thể tăng gấp đôi thành m += 2 * p để chỉ đi qua các bội lẻ của p.
2. Dùng vector<bool> hoặc bitset<MAXN> trong C++ (Tiết kiệm 8 lần bộ nhớ): Một mảng bool isPrime[10000000] thông thường dùng 1 byte cho mỗi phần tử (tốn ~10 MB), trong khi std::bitset<10000001> nén mỗi phần tử vào đúng 1 bit (chỉ tốn ~1.25 MB), giúp toàn bộ bảng sàng nằm gọn trong bộ nhớ đệm L2/L3 Cache của CPU và tăng tốc độ truy cập bộ nhớ rõ rệt.

Khi nào dùng hàm O(√n), khi nào dùng Sàng Eratosthenes?

Lỗi hay gặp

Luyện ngay trên Big-O Coding

Thực hành ngay kiểm tra số nguyên tố, sàng Eratosthenes và kết hợp với mảng cộng dồn qua các bài tập dưới đây trên hệ thống Big-O Coding:

Câu hỏi thường gặp

Nguồn tham khảo

• cp-algorithms: Sieve of Eratosthenes
• CSES Competitive Programmer's Handbook — Chapter 21: Number Theory
• Big-O Coding: Lộ trình Zero-100