這題以前很溫和的...

我用了兩種解法(給大家參考一下)

一.埃拉托斯特尼篩法

這篩法我就不贅述了(自己Google)

重點是題目的測資x的範圍長這樣:2<=x<=2147483647

如果開一個陣列來篩->bool Prime[2147483648];

編譯器就會告訴你:不好意思...先生...你太大了= =

所以我們就只能篩小一點了

我們篩sqrt(2147483647)以下的就好了 註:sqrt是根號

因為我們知道 要檢驗N是不是質數的話

我們只要把N一一除以 小於sqrt(N)的質數 就可以知道他是不是質數了

簡單來說就是(假設測資是N):

1.得到sqrt(2147483647)以下的所有質數->這步驟很快的

2.再把N一一除以我們上面的到的質數

3.恩...就這樣...1.4s喔

二.費馬小定理

費馬小定理也自己Google一下(不會很難理解喔XD)

不贅述了...

簡單來說就是(假設測資是N):

1.得到sqrt(2147483647)以下的所有質數->跟剛剛一樣

2.找出跟N互質的M->用第一步的質數一個一個找(也就是第一個 N%某質數 != 0)

3.看看M^N-1(mod N)等不等於1(等於就可能是質數 不等於就一定不是質數) 註:請用快速冪XD

4.只有第41526筆測資是偽質數(Carmichael Numbers)也就是它等於1但不是質數->這時候就手動輸出ㄅXD(也就是自己放個計數器)

5.恩...就這樣 ...0.7s喔(Yeah~)

大家不要笑我...

我剛剛才發現原來scanf和printf比cin和cout快很多的說...

原來以為cin和cout不用打括弧很棒~

結果...

所以我改成scanf和printf重測後:

1.埃拉托斯特尼篩法:1.0s

2.費馬小定理:0.3s