[HackerRank]Java質數測試(Java Primality Test)

題目描述

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

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

原題網址

輸入格式

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

輸出格式

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

範例輸入

範例輸出

額外解釋

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

解題概念

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

若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");
   }
}