創作內容

2 GP

ZeroJudge - a007: 判斷質數 解題心得

作者:Not In My Back Yard│2018-11-06 22:27:44│巴幣:4│人氣:498
題目連結:


題目大意:
給定一個 X ( 2 ≦ X ≦ 2, 147, 483, 647 ),判斷 X 是否為質數。

註:測試資料最多有 200, 000 筆。



範例輸入:
13
14



範例輸出:
質數
非質數



解題思維:
除了建表(要壓常數時間,不然會TLE)以外,可以使用「米勒-拉賓質性判定法」,在 WIKI 有相當完善的說明和證明。(建議可以先去過目一下,理解原理)

而一般情況來說,「米勒-拉賓判定法」並非確定性演算法(只能判斷出是合數,或是可能是質數)。但是有人求出了int範圍(2147483647)內,只要判斷 2、 7 、 61 即可知道是否是質數。

而且這個演算法十分高效(O( k * log ^ 3 (n))),k是我們測試的值。

由於運算時會碰到次方,因此我們需要快速冪




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。
引用網址:https://home.gamer.com.tw/TrackBack.php?sn=4186689
All rights reserved. 版權所有,保留一切權利

相關創作

同標籤作品搜尋:程式題目解題心得|質數|快速冪

留言共 0 篇留言

我要留言提醒:您尚未登入,請先登入再留言

2喜歡★inversion 可決定是否刪除您的留言,請勿發表違反站規文字。

前一篇:ZeroJudge - ... 後一篇:ZeroJudge - ...

追蹤私訊切換新版閱覽

作品資料夾

klra717大家
邊緣人更新,邊緣人自推。黑暗奇幻《魔王傳》於小屋更新,一人一留言,順手捐發票,救救邊緣人。看更多我要大聲說21分前


face基於日前微軟官方表示 Internet Explorer 不再支援新的網路標準,可能無法使用新的應用程式來呈現網站內容,在瀏覽器支援度及網站安全性的雙重考量下,為了讓巴友們有更好的使用體驗,巴哈姆特即將於 2019年9月2日 停止支援 Internet Explorer 瀏覽器的頁面呈現和功能。
屆時建議您使用下述瀏覽器來瀏覽巴哈姆特:
。Google Chrome(推薦)
。Mozilla Firefox
。Microsoft Edge(Windows10以上的作業系統版本才可使用)

face我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營,請將 gamer.com.tw 加入廣告阻擋工具的白名單中,謝謝 !【教學】