Hướng dẫn giải

Cho số nguyên dương $n$, cần tìm thừa số nguyên tố lớn nhất trong phân tích của $n$. Nếu $n$ là lũy thừa của một số nguyên tố thì thừa số lớn nhất chính là số nguyên tố đó.

Sub 1: Vét cạn — ~O(n)~, dùng khi ~n \le 10^6~

Thử mọi $d$ từ $2$ đến $n$. Mỗi khi $d$ chia hết số còn lại $m$ thì ghi $d$ làm ứng viên và chia $m$ cho $d$ cho đến khi không chia hết nữa. Vì $d$ tăng dần nên ứng viên cuối cùng chính là thừa số nguyên tố lớn nhất.

Kết quả chấm riêng sub này: đúng 10/21 test (các test còn lại quá giờ vì $n$ lớn hơn miền của sub).

Sub 2: Thử đến căn bậc hai — ~O(\sqrt{n})~, dùng cho ~n \le 10^{10}~

Chỉ thử $d$ với $d \cdot d \le m$. Sau vòng lặp, nếu $m > 1$ thì $m$ là một số nguyên tố, và nó lớn hơn mọi ước đã tìm được, nên $m$ là đáp án.

Bẫy cần chú ý: $n$ có thể đến $10^{10}$ nên phải dùng long long. Đừng quên trường hợp phần còn lại $m > 1$ sau vòng lặp, vì đó chính là số nguyên tố lớn nhất khi thừa số lớn nằm ngoài miền thử.

Kết quả chấm riêng sub này: đúng 21/21 test.

Chương trình hoàn chỉnh

Chương trình đọc $T$, rồi với mỗi test đọc $n$. Nếu $n \le 10^6$ thì gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub1 vẫn ăn điểm các test nhỏ nếu sub2 chưa làm kịp.

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

long long n;

// Sub 1: vét cạn — thử mọi d từ 2 đến n, ghi lại thừa số nguyên tố lớn nhất gặp được
// Dùng khi n <= 10^6
void sub1() {
    long long best = 1;
    long long m = n;
    for (long long d = 2; d <= m; d++)
        while (m % d == 0) { best = d; m /= d; }
    cout << best << "\n";
}

// Sub 2: chỉ thử d đến căn bậc hai — dùng cho n lớn (đến 10^10)
// Phần m còn lại (nếu > 1) là một thừa số nguyên tố, và lớn hơn mọi ước đã tìm được
void sub2() {
    long long best = 1;
    long long m = n;
    for (long long d = 2; d * d <= m; d++)
        while (m % d == 0) { best = d; m /= d; }
    if (m > 1) best = m;
    cout << best << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        if (n <= 1000000) sub1();   // n nhỏ: vét cạn cho chắc
        else sub2();                // n lớn: chỉ thử đến căn bậc hai
    }
    return 0;
}