Lại là số nguyên tố

View as PDF

Submit solution


Points: 0.29 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Tìm số nguyên tố gần nhất nhỏ hơn ~N~ ~\left(3 \leq N \leq 2^{32}\right)~.

Input

Dòng đầu tiên chứa số nguyên ~T~ là số lượng test ~\left(T \leq 10000\right)~

~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~N~.

Output

Với mỗi test, in kết quả trên một dòng.

Sample Input

3
5
10
17

Sample Output

3
7
13

Comments

Please read the guidelines before commenting.



  • -1
    NVTai  commented on April 3, 2025, 2:56 p.m. edited

    :)))khoai thiệt chứ, submit gần 20 lần ms ac


  • 5
    YougiTuber  commented on Jan. 16, 2025, 6:02 a.m. edited

    Spoil ⚠️

    Khoảng cách lớn nhất giữa ~2~ số nguyên tố nhỏ hơn ~2^{32}~ là không quá lớn, có thể duyệt trâu để thử (~2~ số cách nhau lớn nhất khoảng ~336~)

    Có thể dùng một thuật kiểm tra số nguyên tố nào đó (Fermat nhỏ hoặc Miller - Rabin) để đạt được thuật toán có độ phức tạp khoảng ~O(t.log(n)^2*336)~.

    Lưu ý:

    Vì ~n \le 2^{32}~ nên cần để kiểu dữ liệu unsigned long long tránh tràn số ở phép nhân.


  • 0
    nn9450898  commented on Nov. 19, 2024, 1:06 p.m.

    ,


  • -7
    ThanhBC1234  commented on Oct. 1, 2024, 1:22 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -10
    duongajaas12  commented on April 11, 2024, 2:46 p.m. edited

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -29
    kaksaki1234  commented on Aug. 24, 2022, 3:37 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.