b032: 質數惡夢 cont.
Tags : Miller-Rabin Test Primality Test Prime 數論
Accepted rate : 4人/5人 ( 80% ) [非即時]
評分方式:
Strictly

最近更新 : 2020-05-01 21:13

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 $

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

注意事項

  1. 本題採「嚴格比對」,不過應該沒有任何影響
  2. 本題為單筆多點的測資,請讀至 EOF,送出前請三思
  3. 本題輸入為小於 $ 2^{64} $ 之整數,建議使用 uint64_t
  4.  敝 OJ 支援 __uint128_t,歡迎多加利用
  5. 強烈建議在本機端跑一次範例測資並通過測試執行再提交 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
沒有發現任何「解題報告」