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

Xem dạng PDF
Gửi bài giải
Điểm: 0,29 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout
Dạng bài
Ngôn ngữ cho phép
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

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 0
    NVTai  đã bình luận lúc 3, Tháng 4, 2025, 14:56 ← chỉnh sửa

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


  • 5
    YougiTuber  đã bình luận lúc 16, Tháng 1, 2025, 6:02 ← chỉnh sửa

    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  đã bình luận lúc 19, Tháng 11, 2024, 13:06

    ,


  • -7
    ThanhBC1234  đã bình luận lúc 1, Tháng 10, 2024, 1:22

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -10
    duongajaas12  đã bình luận lúc 11, Tháng 4, 2024, 14:46 ← chỉnh sửa

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -29
    kaksaki1234  đã bình luận lúc 24, Tháng 8, 2022, 15:37

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.