主題

ZeroJudge - f394: 質數判定 解題心得

Not In My Back Yard | 2020-11-15 00:00:02

題目連結:


題目大意:
輸入有多列(約 500 列),每列給定一正整數(0 < 給定之數值 < 2 ^ 63),請判斷給定的數字是否為一個質數。是的話,請輸出「Yes」;反之,輸出「No」。



範例輸入:
154590409516822759
2305843009213693951
1436697831295441


範例輸出:
Yes
Yes
No


解題思維:
還記得米勒-拉賓質性判定法嗎?本題就是需要使用該演算法,參見這題



雖然題目的本意是讓你隨機從 2 ~ 欲測試數字之值 - 1 的範圍內挑出幾個數字利用上面的方式測該數是否為質數。不過類似於小於 2 ^ 31 的數字只需判斷 2 、 7 、 61 三個數字的情況,有人求出了在 2 ^ 64 以內的數字,丟 2 、 325 、 9375 、 28178 、 450775 、 9780504 、 1795265022 這七個數字進去各自判斷完後出來的質性結果保證正確。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。
41 巴幣: 0

相關創作

更多創作