題目描述
一個質數是一個大於一的自然數,且無法找到除了自己本身和1之外的數能整除它。舉例來說,前六個質數為2、3、5、7、11和13。
給定一個大整數,判斷並輸出這個整數是不是質數。
原題網址
輸入格式
輸入只有一行,為要檢查是不是質數的整數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,已經很足夠了。
參考答案
import java.math.BigInteger;
import java.util.*;
public class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
BigInteger n = in.nextBigInteger();
in.close();
System.out.println(n.isProbablePrime(10) ? "prime" : "not prime");
}
}