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


題目描述

一個質數是一個大於一的自然數,且無法找到除了自己本身和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,已經很足夠了。

參考答案

關於作者

Magic Len

各位好,我是Magic Len,是這網站的管理員。我是台灣台中大肚山上人,畢業於台中高工資訊科和台灣科技大學資訊工程系,曾在桃機航警局服役。我熱愛自然也熱愛科學,喜歡和別人分享自己的知識與經驗。如果你有興趣認識我,可以加我的Facebook,並且請註明是從MagicLen來的。

相關文章