#20494: 本題想法


lawrence910426@gmail.com (l4wr3nc3)

School : 新北市立板橋高級中學
ID : 67988
IP address : [140.114.6.181]
Last Login :
2020-11-09 14:57:43
a007. 判斷質數 | From: [59.115.246.65] | Post Date : 2020-01-30 23:53

本題十分的簡單,相信各位在閱讀完本篇題解後必定能夠解開這題的。

小弟有三個主流方法可以解開這題,以下將詳細的一一介紹。

---------------------------------------------------------------------------------------

一、Miller-Rabin Primilarity Test

先備知識:

(一)、費馬小定理

(二)、快速冪

 

這是一個實作起來十分精簡的隨機演算法,內容大概如下。

(一)、隨機選取一個數字做為測試,以下稱呼該數字為 a

(二)、計算 a^(N-1) mod N,並且判斷 a^(N-1) mod N 是否等於 1 或是 -1。如果是,執行下一步;否則 N 就是合數。

(三)、計算 a^((N-1)/2) mod N,並且判斷 a^((N-1)/2) mod N 是否等於 1 或是 -1。如果是,執行下一步;否則 N 就是合數。

(三)、計算 a^((N-1)/2) mod N,並且判斷 a^((N-1)/2) mod N 是否等於 1 或是 -1。如果是,執行下一步;否則 N 就是合數。

 
ZeroJudge Forum