Content

承 b022，串串睜開眼睛後，發現他還在作惡夢。

現在，惡魔貓男帶著一群很長數字來追殺他。其中，質數是他們的將領。只有找出這些討人厭的質數，才能順利醒來。

所以，請你試設計一程式，有效率地判別一長整數是否為質數。

Input

輸入不超過 426 行。

每行有一非負整數 $ n $ ，且 $ n < 2^{64} $。

請讀至 EOF。

Output

對於每一個 $ n $ ，當 $ n $ 為質數時輸出 'T'，否則輸出 'F'。

Sample Input

1111111111111111111
4611686014132420609
688846502588399
68721049609
99194853094755497
8828119010022395329
2305843009213693951
2147483649
2147483647
948769699487

Sample Output

T
F
T
F
T
F
T
F
T
F

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (100%): 1.0s , <1M

Hint ：

範例說明

$ 1111111111111111111 $ 是個「循環質數」
$ 4611686014132420609 = 2147483647^2 $
$ 688846502588399 $ 是個「盧卡斯質數」
$ 68721049609 = 262147 ^ 2 $
$ 99194853094755497 $ 是個「費波那西質數」
$ 8828119010022395329 = 2971215073^2 $
$ 2305843009213693951 $ 是個「梅森質數」
$ 2147483649 = 3 * 715827883 $
$ 2147483647 $ 是個「雙梅森質數」
$ 94879469 = 31 * 3461 * 8842957 $

你說這些質數是不是很可愛？？>\\\<

注意事項

本題採「嚴格比對」，不過應該沒有任何影響
本題為單筆多點的測資，請讀至 EOF，送出前請三思
本題輸入為小於 $ 2^{64} $ 之整數，建議使用 uint64_t
敝 OJ 支援 __uint128_t，歡迎多加利用
強烈建議在本機端跑一次範例測資並通過測試執行再提交 o'_'o

Tags:

Miller-Rabin Test Primality Test Prime 數論

出處:

[管理者：

nevikw39 ($\mathscr{nevikw}\pmb{39}\in\mathbf{37}^{th}$)

]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」