Number Theory

🔢 Kiểm tra số nguyên tố: Trial, Sieve, Segmented Sieve & Miller–Rabin

Bài học nâng cấp các phương pháp kiểm tra số nguyên tố theo hướng dùng trong thi lập trình hiện nay: chọn đúng thuật toán theo kích thước dữ liệu, sửa các độ phức tạp chưa chuẩn, bổ sung Miller–Rabin xác định cho 64-bit và cách dùng an toàn trong C++/Python.

Trial Division1 số nhỏ
SieveNhiều truy vấn
SegmentedĐoạn [L,R] rất lớn
Miller–RabinN đến 2⁶⁴ và hơn
Tổng quanTrialSàngSegmentedMiller–RabinChọn thuật toánLỗiBài tập

Mục tiêu và bức tranh tổng quan

Học xong cần làm được

  • Hiểu số nguyên tố và vì sao chỉ cần thử đến √n.
  • Biết chọn giữa chia thử, sàng thường, sàng đoạn và Miller–Rabin.
  • Cài đặt code C++/Python an toàn cho dữ liệu lớn.
  • Nhận ra lỗi tràn số, sai độ phức tạp, dùng thuật toán không phù hợp.

Cập nhật quan trọng

  • Sàng Eratosthenes chuẩn có độ phức tạp O(n log log n).
  • Với 64-bit, Miller–Rabin có thể kiểm tra chính xác bằng bộ base cố định.
  • C++ hiện đại dùng __int128 để nhân modulo an toàn.
  • Python dùng pow(a, d, n) đã tối ưu và an toàn cho số lớn.
Dạng bàiThuật toán nên dùngĐộ phức tạpGhi chú
Kiểm tra 1 số nhỏ, ít testTrial DivisionO(√n)Đủ tốt với n ≤ 10⁹ và ít test.
Nhiều truy vấn trong [1,N]Sàng EratosthenesO(n log log n), bộ nhớ O(n)Phù hợp N khoảng 10⁷, tùy bộ nhớ.
Tìm prime trong [L,R], R lớnSegmented SieveO(√R log log √R + độ dài đoạn)Dùng khi R lớn nhưng R-L vừa phải.
Kiểm tra n ≤ 2⁶⁴Miller–Rabin deterministic basesO(k log n)Rất nhanh.
Phân tích thừa số 64-bitMiller–Rabin + Pollard RhoNâng caoMiller–Rabin chỉ kiểm tra prime/composite.

1. Trial Division – chia thử đến √n

Chia thử là nền tảng: nếu n là hợp số thì nó có ít nhất một ước không vượt quá √n.

Nhấn “Bước tiếp” để thử các ước từ 2 đến √n.

Phân tích thuật toán

  • Ý tưởng: nếu n có ước khác 1 và chính nó, thì tồn tại một ước không vượt quá √n.
  • Tối ưu cơ bản: xử lý riêng số chẵn, sau đó chỉ thử các ước lẻ 3, 5, 7, ....
  • Độ phức tạp: O(√n), bộ nhớ O(1).
  • Khi dùng: phù hợp khi chỉ kiểm tra ít số, hoặc n không quá lớn.
bool isPrime(long long n) {
    if (n < 2) return false;
    if (n % 2 == 0) return n == 2;
    for (long long i = 3; i <= n / i; i += 2)
        if (n % i == 0) return false;
    return true;
}
def is_prime(n):
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2
    i = 3
    while i * i <= n:
        if n % i == 0:
            return False
        i += 2
    return True

Giải thích code

  • if (n < 2) return false;: loại 0, 1 và số âm vì không phải số nguyên tố.
  • if (n % 2 == 0) return n == 2;: chỉ số 2 là nguyên tố chẵn; mọi số chẵn lớn hơn 2 đều là hợp số.
  • i <= n / i: tương đương i*i <= n nhưng tránh tràn số trong C++ khi n lớn.
  • i += 2: bỏ qua toàn bộ số chẵn, giảm khoảng một nửa số phép thử.
Lưu ý C++: dùng i <= n / i thay vì i * i <= n để tránh tràn số.

2. Sàng Eratosthenes

Nếu p là nguyên tố, ta gạch các bội số của p bắt đầu từ p².

Nhấn “Bước tiếp” để gạch bội số.

Phân tích thuật toán

  • Ý tưởng: ban đầu coi mọi số từ 2 đến N là nguyên tố, sau đó gạch các bội của từng số nguyên tố.
  • Vì sao bắt đầu từ p*p? Các bội nhỏ hơn p*p đã bị gạch bởi các ước nguyên tố nhỏ hơn p.
  • Độ phức tạp chuẩn: O(n log log n), bộ nhớ O(n).
  • Khi dùng: tốt cho nhiều truy vấn kiểm tra nguyên tố trong phạm vi vừa, ví dụ N ≤ 10^7.
vector<bool> sieve(int n) {
    vector<bool> isPrime(n + 1, true);
    if (n >= 0) isPrime[0] = false;
    if (n >= 1) isPrime[1] = false;
    for (long long p = 2; p * p <= n; p++)
        if (isPrime[p])
            for (long long x = p * p; x <= n; x += p)
                isPrime[x] = false;
    return isPrime;
}
def sieve(n):
    is_prime = [True] * (n + 1)
    if n >= 0: is_prime[0] = False
    if n >= 1: is_prime[1] = False
    p = 2
    while p * p <= n:
        if is_prime[p]:
            for x in range(p * p, n + 1, p):
                is_prime[x] = False
        p += 1
    return is_prime

Giải thích code

  • isPrime[0] = isPrime[1] = false: 0 và 1 không phải số nguyên tố.
  • Vòng ngoài p * p <= n: chỉ cần xét prime đến √n.
  • Vòng trong x = p*p; x += p: gạch lần lượt các bội số của p.
  • Sau khi sàng xong, isPrime[x] == true nghĩa là x là số nguyên tố.
Kiến thức chuẩn: Sàng Eratosthenes có thời gian O(n log log n) và bộ nhớ O(n).

3. Segmented Sieve – sàng trên đoạn [L, R]

Khi R rất lớn, không thể tạo mảng từ 1 đến R. Ta chỉ tạo mảng cho đoạn [L,R] và dùng prime nhỏ đến √R để gạch.

Sàng prime ≤ √R
→
Tạo mark[R-L+1]
→
Gạch bội trong đoạn
→
Ô còn lại là prime
Nhập đoạn có độ dài nhỏ để quan sát.

Phân tích thuật toán

  • Vấn đề: nếu R rất lớn, không thể tạo mảng từ 1 đến R.
  • Ý tưởng: chỉ tạo mảng cho đoạn cần xét [L,R], rồi dùng các prime nhỏ ≤ √R để gạch hợp số trong đoạn.
  • Điểm bắt đầu gạch: max(p*p, ceil(L/p)*p).
  • Bộ nhớ: O(√R + R-L+1), phù hợp khi R lớn nhưng độ dài đoạn vừa phải.
vector<long long> segmentedSieve(long long L, long long R) {
    long long limit = sqrtl(R) + 1;
    vector<bool> small(limit + 1, true);
    small[0] = small[1] = false;
    for (long long p = 2; p * p <= limit; p++)
        if (small[p])
            for (long long x = p * p; x <= limit; x += p)
                small[x] = false;
    vector<long long> primes;
    for (long long p = 2; p <= limit; p++)
        if (small[p]) primes.push_back(p);
    vector<bool> mark(R - L + 1, true);
    for (long long p : primes) {
        long long start = max(p * p, ((L + p - 1) / p) * p);
        for (long long x = start; x <= R; x += p)
            mark[x - L] = false;
    }
    vector<long long> ans;
    for (long long i = 0; i <= R - L; i++)
        if (L + i >= 2 && mark[i]) ans.push_back(L + i);
    return ans;
}
import math

def segmented_sieve(L, R):
    limit = math.isqrt(R) + 1
    small = [True] * (limit + 1)
    if limit >= 0: small[0] = False
    if limit >= 1: small[1] = False
    p = 2
    while p * p <= limit:
        if small[p]:
            for x in range(p * p, limit + 1, p):
                small[x] = False
        p += 1
    primes = [p for p in range(2, limit + 1) if small[p]]
    mark = [True] * (R - L + 1)
    for p in primes:
        start = max(p * p, ((L + p - 1) // p) * p)
        for x in range(start, R + 1, p):
            mark[x - L] = False
    return [L + i for i in range(R - L + 1) if L + i >= 2 and mark[i]]

Giải thích code

  • limit = sqrt(R) + 1: chỉ cần các prime nhỏ đến căn của R.
  • mark[x - L]: ánh xạ số thật x trong đoạn về chỉ số mảng bắt đầu từ 0.
  • start = max(p*p, ((L+p-1)/p)*p): tìm bội đầu tiên của p nằm trong đoạn nhưng không gạch chính p.
  • Cuối cùng, số L+i là prime nếu mark[i] còn true và L+i ≥ 2.

4. Miller–Rabin – kiểm tra nguyên tố hiện đại

Miller–Rabin rất nhanh cho số lớn. Với số 64-bit, dùng bộ cơ số cố định có thể cho kết quả xác định.

Bộ base an toàn hay dùng cho 64-bit: {2, 325, 9375, 28178, 450775, 9780504, 1795265022}. Với Python, pow(a, d, n) đã là lũy thừa modulo nhanh.
Nhập N và cơ số a để quan sát chuỗi bình phương.

Code mẫu Miller–Rabin 64-bit

Phân tích thuật toán

  • Bước 1: tách n-1 = 2^s · d, với d là số lẻ.
  • Bước 2: với mỗi cơ số a, tính x = a^d mod n bằng lũy thừa nhị phân.
  • Bước 3: bình phương liên tiếp x; nếu gặp n-1 thì cơ số này không chứng minh được n hợp số.
  • Độ phức tạp: khoảng O(k log n) phép nhân modulo, với k là số cơ số kiểm tra.
  • Cập nhật: với số 64-bit, dùng bộ base cố định để kiểm tra xác định; C++ dùng __uint128_t để nhân modulo an toàn.
using u64 = unsigned long long;
using u128 = __uint128_t;

u64 mod_mul(u64 a, u64 b, u64 mod) {
    return (u128)a * b % mod;
}

u64 mod_pow(u64 a, u64 d, u64 mod) {
    u64 res = 1;
    while (d > 0) {
        if (d & 1) res = mod_mul(res, a, mod);
        a = mod_mul(a, a, mod);
        d >>= 1;
    }
    return res;
}

bool check_composite(u64 n, u64 a, u64 d, int s) {
    u64 x = mod_pow(a, d, n);
    if (x == 1 || x == n - 1) return false;
    for (int r = 1; r < s; r++) {
        x = mod_mul(x, x, n);
        if (x == n - 1) return false;
    }
    return true;
}

bool isPrime64(u64 n) {
    if (n < 2) return false;
    for (u64 p : {2ULL,3ULL,5ULL,7ULL,11ULL,13ULL,17ULL,19ULL,23ULL,29ULL,31ULL,37ULL})
        if (n % p == 0) return n == p;
    int s = 0;
    u64 d = n - 1;
    while ((d & 1) == 0) d >>= 1, s++;
    for (u64 a : {2ULL,325ULL,9375ULL,28178ULL,450775ULL,9780504ULL,1795265022ULL}) {
        if (a % n == 0) continue;
        if (check_composite(n, a, d, s)) return false;
    }
    return true;
}
def is_prime_miller_rabin(n):
    if n < 2:
        return False
    for p in [2,3,5,7,11,13,17,19,23,29,31,37]:
        if n % p == 0:
            return n == p
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    bases = [2, 325, 9375, 28178, 450775, 9780504, 1795265022]
    for a in bases:
        if a % n == 0:
            continue
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

Giải thích code

  • mod_mul: tính a*b mod n bằng __uint128_t, tránh tràn số khi a, b gần giới hạn 64-bit.
  • mod_pow: lũy thừa nhị phân modulo, dùng để tính a^d mod n nhanh trong O(log d).
  • check_composite: kiểm tra một cơ số a có chứng minh được n là hợp số hay không.
  • small_primes: lọc nhanh các số nhỏ và số chia hết cho prime nhỏ.
  • bases: bộ cơ số đặc biệt giúp Miller–Rabin chính xác cho phạm vi 64-bit.
Với số vượt 64-bit trong C++: cần big integer library. Với Python, số nguyên lớn được hỗ trợ sẵn, nhưng Miller–Rabin với vài base là kiểm tra xác suất nếu vượt miền chứng minh của bộ base.

5. Cách chọn thuật toán trong đề thi

Ràng buộc đềDấu hiệuChọnKhông nên chọn
n ≤ 10⁹, ít testChỉ hỏi một vài sốTrial Division tối ưuSàng lớn
N ≤ 10⁷, nhiều truy vấnCần kiểm tra prime nhiều lầnSàng + prefix countChia thử từng truy vấn
L,R ≤ 10¹², R-L ≤ 10⁶Đoạn lớn nhưng ngắnSegmented SieveSàng từ 1 đến R
n ≤ 10¹⁸Kiểm tra từng số rất lớnMiller–Rabin 64-bitTrial Division
Cần phân tích thừa sốKhông chỉ hỏi prime/compositeMiller–Rabin + Pollard RhoChỉ Miller–Rabin

6. Lỗi học sinh hay nhầm

Nhầm độ phức tạp sàng.
Sàng Eratosthenes chuẩn là O(n log log n).
Quên xử lý 0, 1.
0 và 1 không phải số nguyên tố.
Tràn số khi kiểm tra i*i ≤ n.
C++ nên dùng i ≤ n / i.
Segmented Sieve gạch sai điểm bắt đầu.
Dùng max(p*p, ceil(L/p)*p).
Miller–Rabin nhưng nhân modulo bị tràn.
C++ 64-bit nên dùng __int128.

7. Bài tập vận dụng

📘 Cơ bản

  1. Kiểm tra một số có phải nguyên tố không.
  2. Đếm số nguyên tố trong mảng nhỏ.
  3. Liệt kê số nguyên tố ≤ N.

📗 Trung bình

  1. Q truy vấn “x có phải prime không?”.
  2. Prefix count số lượng prime trong đoạn.
  3. Sàng SPF để phân tích thừa số nhiều số.

📙 Nâng cao

  1. Segmented Sieve cho [L,R] lớn.
  2. Tìm prime gần nhất ≥ N với N ≤ 10¹⁸.
  3. Đếm số gần nguyên tố trong đoạn.

🐉 HSG định hướng

  1. Miller–Rabin + Pollard Rho.
  2. Prime path bằng BFS.
  3. Prime + DP/Graph.

Quiz kiểm tra nhanh

Câu 1. Sàng Eratosthenes chuẩn có độ phức tạp thời gian nào?
Câu 2. Với n ≤ 10¹⁸, kiểm tra từng số rất lớn nên dùng gì?
Câu 3. Trong Segmented Sieve, vì sao dùng max(p*p, ceil(L/p)*p)?

Tổng kết

Không có một cách kiểm tra số nguyên tố tốt nhất cho mọi bài. Chia thử dùng cho ít số nhỏ, sàng dùng cho nhiều truy vấn trong phạm vi vừa, sàng đoạn dùng cho đoạn lớn, và Miller–Rabin là lựa chọn hiện đại cho số rất lớn.
⬅️ Quay lại chương 12