Hiểu bài toán

Cho một số nguyên dương N. Tìm ba số nguyên dương phân biệt a, b, c sao cho:

1. a, b, c là số nguyên tố
2. a < b < c
3. a² + b² = c²
4. c < N Nếu có nhiều bộ, in ra bất kỳ. Nếu không có, in -1.

Đề bài này thực chất là tìm các bộ ba Pythagore (a, b, c) trong đó cả ba số đều là số nguyên tố và nhỏ hơn N.

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

Cách Brute Force (Lặp kép kiểm tra)

#include <bits/stdc++.h>
using namespace std;

bool nt(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0) return false;
    return true;
}

int main() {
    freopen("nicenum.inp", "r", stdin);
    freopen("nicenum.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    bool found = false;

    for (int a = 2; a < N; a++) {
        if (!nt(a)) continue;
        for (int b = a + 1; b < N; b++) {
            if (!nt(b)) continue;
            int c = a * a + b * b;
            // Kiểm tra tràn số và điều kiện c < N
            if (c >= N) break; 
            if (nt(c)) {
                cout << a << " " << b << " " << c << "\n";
                found = true;
            }
        }
    }
    if (!found) cout << -1;
    return 0;
}

• Time Complexity: O(N * sqrt(N)) ~ 10^9
• Space Complexity: O(1)

Phương pháp này sử dụng hai vòng lặp lồng nhau để sinh tất cả các cặp (a, b) có a < b. Với mỗi cặp, tính c = a² + b². Nếu c < N và cả a, b, c đều là số nguyên tố thì in ra.

• Hàm nt(n) kiểm tra tính nguyên tố bằng cách lặp từ 2 đến căn bậc hai của n.
• Vòng lặp ngoài chạy từ 2 đến N-1, vòng lặp trong chạy từ a+1 đến N-1.
• Điều kiện if (c >= N) break; giúp tăng tốc độ vì nếu b tăng thì c sẽ tăng, vượt quá N thì không cần xét các b lớn hơn.

Độ phức tạp: O(N² * sqrt(N)) do có khoảng N² cặp (a, b) và mỗi lần kiểm tra nguyên tố mất O(sqrt(N)). Với N nhỏ (ví dụ 10^5 hoặc 10^6), phương pháp này có thể chấp nhận được, nhưng với N lớn sẽ rất chậm.

Cách Tối ưu với Sieve of Eratosthenes

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    freopen("nicenum.inp", "r", stdin);
    freopen("nicenum.out", "w", stdout);

    long long N;
    cin >> N;

    vector<bool> prime(N, true);
    prime[0] = prime[1] = false;

    for (long long i = 2; i * i < N; i++) {
        if (prime[i]) {
            for (long long j = i * i; j < N; j += i)
                prime[j] = false;
        }
    }

    vector<long long> primes;
    for (long long i = 2; i < N; i++)
        if (prime[i]) primes.push_back(i);

    bool found = false;
    int P = primes.size();

    for (int i = 0; i < P; i++) {
        long long x = primes[i];
        for (int j = i + 1; j < P; j++) {
            long long y = primes[j];
            long long z = x * x + y * y;
            if (z >= N) break; // Tăng tốc độ
            if (prime[z]) {
                cout << x << " " << y << " " << z << "\n";
                found = true;
            }
        }
    }

    if (!found) cout << -1;
    return 0;
}

• Time Complexity: O(N log log N + P²)
• Space Complexity: O(N)

Đây là phiên bản tối ưu hóa của Brute Force.

1. Sieve of Eratosthenes: Sử dụng mảng boolean prime để đánh dấu các số nguyên tố từ 0 đến N-1. Điều này giúp kiểm tra tính nguyên tố trong thời gian O(1).
2. Danh sách số nguyên tố: Tạo một vector primes chứa tất cả các số nguyên tố nhỏ hơn N. Điều này giảm số lượng vòng lặp đáng kể vì ta chỉ cần xét các số trong danh sách này thay vì tất cả các số tự nhiên.
3. Vòng lặp lồng: Duyệt qua các cặp số nguyên tố (x, y) trong vector primes. Tính z = x² + y².
   • Kiểm tra if (z >= N) break;: Do vector primes được sắp xếp tăng dần, khi y tăng, z sẽ tăng. Nếu z vượt quá N, ta có thể thoát vòng lặp trong sớm.
   • Kiểm tra if (prime[z]): Tra cứu mảng đã đánh dấu để kiểm tra z có phải số nguyên tố không.

Độ phức tạp: O(N log log N) cho Sieve và O(P²) cho vòng lặp kép, trong đó P là số lượng số nguyên tố nhỏ hơn N (khoảng N / ln N).

Cách Tối ưu hóa cấu trúc (Mathematical Insight)

#include <bits/stdc++.h>
using namespace std;

int main() {
    freopen("nicenum.inp", "r", stdin);
    freopen("nicenum.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long N;
    cin >> N;

    // Sieve
    vector<bool> prime(N, true);
    prime[0] = prime[1] = false;
    for (long long i = 2; i * i < N; i++) {
        if (prime[i]) {
            for (long long j = i * i; j < N; j += i) prime[j] = false;
        }
    }

    bool found = false;

    // Lọc theo tính chất Pythagore và số nguyên tố
    // a^2 + b^2 = c^2. Nếu a, b, c đều là số nguyên tố.
    // Số nguyên tố duy nhất chia hết cho 3 là 3.
    // Trừ bộ (3, 4, 5) và các biến thể, các số Pythagore đều chẵn hoặc chia hết cho 3.
    // Vì a, b, c là số nguyên tố > 2 thì phải là số lẻ.
    // Nếu a, b đều lẻ thì a^2 + b^2 chẵn -> c chẵn -> c phải là 2.
    // Nhưng 2^2 = 4, a^2 + b^2 >= 3^2 + 5^2 = 34 > 4. Vô lý.
    // => Một trong hai số a, b phải là 2.
    // => a = 2, b là số nguyên tố lẻ.
    // => c^2 = 4 + b^2. c phải là số nguyên tố.

    // Chỉ cần xét a = 2, b lặp qua các số nguyên tố lẻ.

    if (N > 2) {
        for (long long b = 3; b < N; b += 2) { // Bỏ qua số chẵn (trừ 2)
            if (!prime[b]) continue;
            long long c_sq = 4 + b * b;
            if (c_sq >= N * N) break; // Cẩn thận với tràn số và điều kiện break
            long long c = sqrt(c_sq);
            // Kiểm tra xem c có phải số nguyên không và có bằng căn bậc hai không
            if (c * c == c_sq && c < N && prime[c]) {
                cout << "2 " << b << " " << c << "\n";
                found = true;
            }
        }
    }

    if (!found) cout << -1;
    return 0;
}

• Time Complexity: O(N log log N)
• Space Complexity: O(N)

Đây là phương pháp tối ưu nhất dựa trên toán học.

Tại sao chỉ cần xét a = 2? Giả sử a, b, c là ba số nguyên tố phân biệt thỏa mãn a² + b² = c².

• Nếu a > 2 và b > 2, thì a và b đều là số lẻ.
• Tích của hai số lẻ là số lẻ, bình phương của số lẻ là số lẻ.
• a² + b² = số lẻ + số lẻ = số chẵn.
• Do đó, c² là số chẵn, suy ra c là số chẵn.
• Số nguyên tố chẵn duy nhất là 2.
• Nếu c = 2, thì a² + b² = 4. Không có hai số tự nhiên phân biệt a, b ≥ 2 thỏa mãn.
• Do đó, không thể có cả a > 2 và b > 2.

Kết luận: Một trong hai số a hoặc b phải là 2. Vì đề bài yêu cầu a < b, ta suy ra a = 2.

Thuật toán:

1. Sử dụng Sieve để tạo mảng đánh dấu số nguyên tố.
2. Chỉ cần lặp b chạy qua các số nguyên tố lẻ (bắt đầu từ 3).
3. Tính c² = 4 + b².
4. Kiểm tra xem c² có phải là số chính phương của một số nguyên tố c < N hay không.

Điều này giảm độ phức tạp vòng lặp kép xuống vòng lặp đơn O(N), rất hiệu quả.

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

Bài học kinh nghiệm

• Cấu trúc Pythagore: a² + b² = c². Nếu a, b, c đều là số nguyên tố, thì một trong hai số a hoặc b phải là 2. Đây là chìa khóa để tối ưu hóa bài toán từ O(N²) xuống O(N).
• Sử dụng Sieve of Eratosthenes để kiểm tra tính nguyên tố trong O(1) sau khi tiền xử lý, giúp tăng tốc độ đáng kể so với việc kiểm tra lặp lại trong vòng lặp.

Lỗi thường gặp

• Tràn số (Integer Overflow): Khi tính a² + b², cần dùng kiểu dữ liệu có kích thước đủ lớn (như long long trong C++) để tránh tràn số, đặc biệt khi N lớn.
• Hiệu suất vòng lặp: Trong cách tiếp cận Brute Force, nếu không có điều kiện break hợp lý khi c >= N, hoặc không tối ưu hóa việc kiểm tra số nguyên tố, chương trình có thể bị TLE (Time Limit Exceeded).