logo 首頁 > 文匯報 > 教育 > 正文

【奧數揭秘】質數

2021-04-28

這次的問題,要留意數字有什麼特別,加點聯想力,才比較容易解決。

問 題:整數999039是四個質數之積,求當中最大的質數。

答 案:留意到

999039 = 1000000 - 961 = 10002 - 312 = (1000 + 31)(1000 - 31) = 1031 × 969。

其中969 = 3 × 17 × 19,因此最大質數為1031。

解題過程中,先要留意原本的數跟一百萬很接近,然後計算到相差後,又能聯想起961是31的平方,之後用上了平方差的痤它“@分解,分解969時,發現了3個質因數,而題目裡說質因數有4個,因此其餘的一個必是1031。

其實,比較嚴謹的做法是再檢查一下1031是否質數。題解裡的做法是假設了題目沒有出錯,才確定了1031是質數。判斷1031是否質數,可以用一些較小的質數試一下,看看能否整除它,由2,3,5,7,...開始,試到31就可以了。

關於質數判斷的問題,在中小學階段,基本上就要有整除性的知識,比如2,3,5和11的整除性,那樣能快速篩選了一些非質數出來。7的整除性固然也是有的,網上也會找到不少方法,只是想法多是有點煩瑣,所以比較少提及。除了整除性的知識,還要知道大概檢查到哪個數可以停下來。例如對於正整數n來說,只需要檢查到[n] 或以前的質數就可以了。

至於為什麼是[n] ,要理解也挺容易的,比如考慮n為16,那麼找因數時,可以把16分解為:16 = 1 × 16 = 2 × 8 = 4 × 4

觀察乘式左方的數字,1、2和4由小至大排列,右方16、8和4,由大至小排列,而底部剛好就是[16]  = 4。那麼找因數時,關鍵是只需要找乘式左方數字裡的質數就可以了,即使n本身不是平方數也可以這樣。這個想法,其實小學時也可能不自覺用過,比如找因數時,見茯O16,就找些質數去除,比如試2、3和5,除到5時,商是3,有餘數,發覺除數比商大,那就停下來,當中也是隱含了類似的想法。

這些質數判定的問題歷史悠久,數論裡會有些用上了同餘算術的篩法,能夠把一些質數篩選出來。奧數裡有費馬小定理,也可以判斷什麼不是質數。費馬小定理說的是若p為質數,則對於任意正整數a,p能整除ap - a。這裡省去了一些數論裡常用的同餘符號,希望比較易明。舉例來說,3為質數,就有23 - 2 = 6 = 3 × 2。要是想測試一個正整數p是否質數,可以挑選一個正整數a和這個p,算一算ap - a能否被p整除,若果不行,就知道p不是質數。這些運算過程,若懂同餘算術會做得比較簡單,奧數裡會有相關訓練,課內則沒有。

質數判定這個問題,若是想學得深入一點,難免都要學多些數論,中學生能夠學懂一些初等數論,做到相當多的練習,已經挺難得,但那些還只是基礎而已。有興趣的同學,可以找些初等數論看虒掑@試,看看能否理解。●張志基

●香港數學奧林匹克學校

簡介:奧校於1995年成立,為香港首間提供奧數培訓之註冊慈善機構(編號:91/4924),每年均舉辦「香港小學數學奧林匹克比賽」,旨在發掘在數學方面有潛質的學生。學員有機會選拔成為香港代表隊,獲免費培訓並參加海內外重要大賽。詳情可瀏覽:www.hkmos.org。

讀文匯報PDF版面

新聞排行
圖集
視頻