## 【26】 Quadratic primes二次質數生成多項式 Euler公佈了一個著名的式子: n²+n+41 當n=0~39時它可以得到40個質數,不過當n=40時,40²+40+41=40(40+1)+41可以被41整除,故當n=41時得到的不是質數。 通過電腦分析,一個更不可思議的公式誕生了。n²-79n+1601能產生80個質數若n=0~79。兩個係數-79和1601的積是-126479。 現在來看看下面的公式: n²+an+b且|a|<1000,|b|<1000 |n|表示n的絕對值,如|11|=11,|-4|=4。 找出合適的係數a和b,使得當n從0開始遞增時,得到最多的連續的質數項,並把a和b的積求出來。 先來做一個函式,用來判斷質數 將比n 小的數從2開始,一個一個除除看,若n能被整除,那n就不是質數! ### 【練習1】下面函數用來判斷輸入的數是否質數 ,數不大則效率尚可,但數很大還是不行! ![](https://i.imgur.com/SafO47W.png) ### 練習2】測試n2+n+41,是否真的當n=0~39時它可以得到40個質數 ![](https://i.imgur.com/LexGAAR.png) 當a=1、b=41,這個函數是g(n,1,41)=n2+n+41 g(0,1,41)、g(1,1,41)、……、g(39,1,41) 手動一個一測試太麻煩!用迴圈處理,碰到非質數就停止。 ![](https://i.imgur.com/Ehe3QWF.png) max是否等於40呢? 請你自己再測試n2-79n+1061,看看max是否等於80呢? 接著就要試一下n2+a*n+b,當不同的a、b組合,能找到多少連續含數值都是質數呢? ![](https://i.imgur.com/efgJ10k.png) ### 問題:n2+a*n+b,含數值可能是負的,這就會影響質數的判斷, 你必須保證含g(x,a,b)函數值是正數,才代入isPrime函式判斷。 或者說,g(x,a,b)函數值是負數就不必判斷。 解決上面問題後,剩下的就容易了,你只要記住max產生時的a、b值,我們要求的是a*b阿!