Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Giải thuật] Kiểm tra số nguyên tố Miller-Rabin xác định

    Cho qqq số nguyên. Với mỗi số nnn, hãy xác định nó có phải số nguyên tố hay không. Dùng kiểm tra Miller-Rabin với tập nhân chứng cố định {2,3,5,7,11,13,17,19,23,29,31,37}\{2,3,5,7,11,13,17,19,23,29,31,37\}{2,3,5,7,11,13,17,19,23,29,31,37} (xác định đúng với mọi n<3.3⋅1024n < 3.3\cdot10^{24}n<3.3⋅1024).

    In YES nếu là số nguyên tố, ngược lại NO.

    • Định dạng đầu vào:

      Dòng đầu: qqq. Tiếp theo là qqq số nnn (mỗi số trên một dòng hoặc cách nhau bởi khoảng trắng).

    • Ràng buộc đầu vào:

      1≤q≤1041 \le q \le 10^41≤q≤104, 0≤n≤10180 \le n \le 10^{18}0≤n≤1018.

    • Định dạng đầu ra:

      qqq dòng, mỗi dòng YES hoặc NO.

    Ví dụ:

    Đầu vào:

    4
2
15
97
1000000007

    Đầu ra:

    YES
NO
YES
YES

    Giải thích:

    2 và 97 và 1000000007 là số nguyên tố (YES); 15 = 3×5 hợp số (NO).

    Đang tải editor...