[Tips]如何找出質數(Prime Numbers)?

  • 26775
  • 0
  • Tips
  • 2010-03-02

[Tips]如何找出質數(Prime Numbers)?

image

最近正在看ㄧ本書- 質數的孤獨。書內的頁碼編排剛好就是以質數的方式呈現。

這讓筆者聯想到要怎樣透過程式碼去找出質數? 我們來試看看吧!

 

首先,要針對「質數」做定義:質數是大於1的一個數字,除了1跟本身之外,沒有其他的自然數能整除它。

 

根據這個定義,很明顯的偶數除了2之外,都出局了。

 

針對奇數來講,像是9就不是質數,它是由兩個質數3相乘所組成,15則等於3乘以5,21則是3乘以7..

由上述算法看來,非質數的奇數都是由多個小於其之質數連乘積所構成。

 

9=3x3

15=3x5

21=3x7

27=3x3x3

 

 

因此,透過上述的概念,我們就可以知道,如果奇數無法被小於本身的質數除盡,它就是個質數。

如此就可以寫出下列程式碼(判斷1000內的質數有哪些?):

image

 

 

 

 

顯示的結果:

image

 

 

 

如果要判斷一個數字是否為質數,還可以利用下列簡潔的寫法:


(updated: 2010/03/02)

 

概念一樣,但是透過牛頓的因式檢驗法,只要去過濾所有小於根號n的質數就可以了。

n是合成數,必有一個小於根號n的質因數。如 3,5,7,11,13…等等。

 

 

 

 

 

 

 

參考資料:

http://www.daniweb.com/code/snippet216900.html

http://bbs.mychat.to/reads.php?tid=216667

http://episte.math.ntu.edu.tw/articles/mm/mm_04_4_04/page2.html

 

 

 

如果您有微軟技術開發的問題,可以到MSDN Forum發問。

如果您有微軟IT管理的問題,可以到TechNet Forum發問喔。