Hiểu bài toán

Bài toán yêu cầu kiểm tra một số nguyên n có phải là số nguyên tố hay không. Số nguyên tố là số nguyên dương lớn hơn 1 và chỉ có hai ước số là 1 và chính nó. Với giới hạn |n| <= 10^12, ta cần một thuật toán đủ nhanh để xử lý các số lớn. Tuy nhiên, do n có thể là số âm hoặc 0, ta phải xử lý các trường hợp này trước (chúng không phải số nguyên tố).

Các cách tiếp cận

Cách Brute Force (Duyệt qua tất cả các số)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(){
    int n ; 
    scanf("%d", &n);
    if(n <= 1){
        printf("NO");
        return 0;  
    }  else if(n == 2){
        printf("YES");
    } else {
        for (int i = 2; i*i <= n; i++){
            if(n % i == 0){
                printf("NO"); 
                return 0; 
            } 
        } 

    printf("YES");
}
    return 0; 
}

• Time Complexity: O(sqrt(n))
• Space Complexity: O(1)

Đây là cách tiếp cận cơ bản nhất. Ta kiểm tra n từ 2 đến căn bậc hai của n. Nếu tìm được ước số nào thì n không nguyên tố. Tuy nhiên, code này chỉ xử lý được số nguyên 32-bit (int), không thỏa mãn giới hạn 10^12 (cần long long).

Cách Optimized Trial Division (Tối ưu hóa lẻ)

#include <stdio.h>
#include <stdbool.h>
#include <math.h>

bool test(long long k){
    if (k < 2) return false;
    if (k % 2 == 0) return k == 2;
    for (long long i = 3; i * i <= k; i+=2)
        if (k % i == 0) return false;
    return true;
}

int main(){
    long long n;

    scanf("%lld", &n);
    if (test(n)) printf("YES");
    else printf("NO");

    return 0;
}

• Time Complexity: O(sqrt(n))
• Space Complexity: O(1)

Đây là thuật toán chuẩn để kiểm tra tính nguyên tố cho các số lớn trong phạm vi 10^12. Nó sử dụng kiểu dữ liệu long long để lưu trữ số. Các tối ưu hóa bao gồm:

1. Kiểm tra chẵn lẻ: Sau khi kiểm tra số 2, ta chỉ cần duyệt các số lẻ từ 3 trở đi (tăng bước nhảy là 2).
2. Kiểm tra điều kiện dừng: Duyệt chỉ đến i * i <= k thay vì sqrt(k) để tránh tràn số hoặc lỗi kiểu số thực. Với 10^12, sqrt(10^12) = 10^6, số lượng vòng lặp khoảng 500,000 (số lẻ), hoàn toàn chấp nhận được.

Cách Deterministic Miller-Rabin (Tham khảo)

#include <bits/stdc++.h>
using namespace std;
using u64 = uint64_t;
using u128 = __uint128_t;

u64 power(u64 a, u64 b, u64 m) {
    u64 res = 1;
    a %= m;
    while (b > 0) {
        if (b & 1) res = (u128)res * a % m;
        a = (u128)a * a % m;
        b >>= 1;
    }
    return res;
}

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

bool isPrime(u64 n) {
    if (n < 2) return false;
    int r = 0;
    u64 d = n - 1;
    while ((d & 1) == 0) {
        d >>= 1;
        r++;
    }
    // Căn chỉnh các witness cho n < 2^64
    for (u64 a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
        if (n == a) return true;
        if (check_composite(n, a, d, r)) return false;
    }
    return true;
}

int main() {
    long long n;
    cin >> n;
    if (isPrime(n)) cout << "YES";
    else cout << "NO";
    return 0;
}

• Time Complexity: O(k log^3 n) (hằng số nhỏ)
• Space Complexity: O(1)

Miller-Rabin là thuật toán xác suất, nhưng với các số n < 2^64 (lớn hơn nhiều so với 10^12), ta có thể dùng một bộ các số witness cố định để biến nó thành thuật toán xác định (Deterministic). Nó nhanh hơn nhiều so với Trial Division khi n rất lớn. Tuy nhiên, với 10^12, Trial Division đã đủ nhanh và dễ hiểu hơn.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Độ phức tạp thuật toán duyệt ước cần thấp hơn O(n). O(sqrt(n)) là chấp nhận được với n <= 10^12.
• Phải sử dụng long long (hoặc unsigned long long) trong C/C++ để tránh tràn số khi n lên tới 10^12.
• Chỉ cần kiểm tra các ước số lẻ sau khi đã loại trừ trường hợp chẵn.

Lỗi thường gặp

• Quên xử lý các trường hợp đặc biệt: n <= 1 không phải là số nguyên tố.
• Sử dụng biến int thay vì long long dẫn đến lỗi tràn số (Overflow) và sai kết quả.
• Viết điều kiện vòng lặp là i < sqrt(n) thay vì i * i <= n. Hàm sqrt trả về số thực, có thể gây sai lệch precision nếu không cẩn thận, hoặc overhead không cần thiết.