Bạn đã viết chương trình kiểm tra số nguyên tố? OK, chắc là bạn đã làm và rất tự tin với đoạn mã của mình. Tuy nhiên, bạn sẽ gặp rắc rối ở đây. Bởi đề bài chúng tôi đưa ra ở đây là n cỡ 10¹⁸, đó là một vấn đề. Hiện tại chưa có thuật toán đúng để giải nó mà chỉ có các giải thuật xác suất. Nếu bạn có khả năng nghe được tiếng Anh thì hãy truy cập link dưới đây.

https://www.youtube.com/watch?v=SSpcBIM9Gb8

Hoặc có thể đọc trên wiki về giải thuật sau: 

https://vi.wikipedia.org/wiki/Ki%E1%BB%83m_tra_Miller-Rabin

Hãy nghiên cứu thật kỹ rồi code nhé!

Yêu cầu: Viết chương trình kiểm tra một số có nguyên tố hay không?

Dữ liệu: 

-  Dòng 1 ghi số lượng số cân kiểm tra t (0<t<=10³)

- t dòng kế tiếp ghi t số nguyên dương n(0<n<=10¹⁸)

Kết quả: 

- In ra t dòng ghi YES hoặc NO nếu số tương ứng là nguyên tố hoặc không.