[HackerRank]Java質數檢查器(Java Prime Checker)

題目描述

您將會得到一個Solution類別和一個main方法,您必須要建立一個Prime類別,並在Prime類別之中實作一個checkPrime方法,讓程式可以正確地輸出質數

原題網址

https://www.hackerrank.com/challenges/prime-checker

輸入格式

共有五行輸入,每一行輸入包含一個整數。

輸出格式

共有四行輸出,每第n行輸出包含所有大於等於第一行輸入且小於等於第n + 1行輸入整數的質數

範例輸入

2
1
3
4
5

範例輸出

2
2
2 3
2 3 5

解題概念

由於題目會需要進行4次在一個範圍內搜尋質數的動作,因此我們一開始如果就先建好一個適當範圍的質數表,之後遇到符合範圍內的數字只要查表就可以知道該數字是否為質數,不符合範圍的數字再去計算是否為質數,如此一來程式的執行時間會大大縮減。

至於要判斷一個數字是否為質數,那就要找出大於等於2或小於自己本身的數字範圍中,有沒有哪個數字可以整除自己,如果都沒有的話就代表自己本身就是質數。然而事實上,單純使用用這種方式進行質數判斷,效率是很差的,比如要判斷10000是否為質數,豈不是要把2、3、4、5、… 、9999都拿來除看看10000測試是否能整除?若是能使用以下兩種方式來篩選除數,就能大大減少判斷質數的速度:

  • 把要拿來測試的除數分為單數和偶數兩個部份的話,偶數只需拿「2」來測試即可,因為能整除以「4」、「6」、「8」等等偶數的數必定也能整除以「2」。
  • 最大的除數只需取到被除數開根號的無條件捨棄值即可,因為如果有大於或等於這個值的數可以整除被除數,必定又有小於或等於這個值的數可以整除被除數。

那麼質數表該如何建立呢?其實觀察所有質數可以發現,質數必定為6n+1或是6n-1(6的倍數加1或減1),所以只要從中找出質數即可。質數必定為6n+1或是6n-1的證明如下:

若使用6n、6n+1、6n+2、6n+3、6n+4、6n+5來表示所有整數,6n必可用「6」整除和「2」整除,6n+2和6n+4必可用「2」來整除,6n+3=3(2n+1)必可用「3」來整除,所以質數只能是6n+1或是6n+5,而6n+5也可以表示為6(n+1)-1、6n-1。

把沒有必要拿來測試是否為質數數字先排除掉,如此一來質數表的建立就會快上好幾倍!

參考答案

關於作者

Magic Len

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

相關文章