題目描述

一個質數是一個大於一的自然數,且無法找到除了自己本身和1之外的數能整除它。舉例來說,前六個質數為2、3、5、7、11和13。



給定一個大整數,判斷並輸出這個整數是不是質數。

原題網址

https://www.hackerrank.com/challenges/java-primality-test

輸入格式

輸入只有一行,為要檢查是不是質數的整數n。範圍在1到10101之間(包含1但不包含10101)。

輸出格式

如果n是質數,輸出「prime」,否則輸出「not prime」。

範例輸入

13

範例輸出

prime

額外解釋

13只能被1和13給整除,所以是質數。

解題概念

產生n的BigInteger物件,並用isProbablePrime方法來判斷整數n是不是質數。isProbablePrime需傳入一個精確值參數certainty,數值愈大計算出來的結果正確率愈高,相對需要更多的時間。正確率公式如下:

正確率 = 1 - (1 / 2certainty)

若certainty=10,正確率就有0.999023438,已經很足夠了。

參考答案