為了確定我寫的有沒有問題,

我還特地寫一個for迴圈跑到10000000,

判斷個數為  質數個數664579,

這還是一個一個慢慢跑,

若從取質數做判定拆成兩塊來看

我敢說我的寫法在判定應該沒有更快的

但是取數目那地方應該還有更好的寫法

若這寫法逾時的話

那應該不會到83%

為什麼我那麼肯定,

因為我念過整數論- - 

積八毛,寫了半天,結果資測bug

自己都沒寫好- - 

我還是直接說明我的程式邏輯吧

如果看得懂得上述程式碼的話這段應該就不用看

畢竟看別人的邏輯是很痛苦的一件事情

我如何判定質數?

判定方法很簡單,就是判定小於此數開根號的所有因數,

至於這塊我看大多數人最多只判定小於他的奇數,

而小於他開根號的質數從哪來?

這就是用遞迴的方式得到的

若開根號的數大於我的質數表呢?

這我就是取for迴圈,沒錯 這方面我是從我的最大質數跑到

小於等於我開根號的數,(這邊就真的只是用奇數在跑,我想這塊還可以再改進)

如果還是不懂的話建議把質數的定義在看熟一點,

這邊我推薦數論(整數論),將會對這塊有很大的幫助,

有幾個提示可以想想看,不過這要寫出來真的是有點難

1.要怎麼判定質數? 判定小於等於他開根號的所有質數即可

2.要怎麼確定他是小魚等於開根號裡面的最大質數?

這幾個是很有趣的,可以多想想看 

再者,我不清楚資測那邊是怎麼測,我自己寫了兩個for迴圈去抓我那程式的質數

1000000 78498

10000000 664579

跑出來的質數個數都對,我不清楚資測測哪個數是我判定錯的

我不敢說我的程式沒有bug,但我可以說最起碼跑到 10000000 止

我判定他為質數,然後做加總,個數是對的,所以我才猜測資測的數是錯誤的 

判定方法很簡單,就是判定小於此數開根號的所有因數, > 質數

找不到編輯選項,肝~ 

不好意思，小弟目前就讀國中一年級

實在不懂太多的數學相關知識

因此決定利用樓主經過數論縝密思考後的程式來驗證我對質數的認知

我有一位強者同學心算出2147483647是一個質數

我覺得很扯，所以決定用樓主的程式來確定他的說法

接著 神奇的事情

發生了

我第一次輸入2147483647時，樓主的程式稍微頓了一下

不過還是算很快地算出了2147483647是一個質數

我的朋友覺得很有趣

所以他馬上又輸入了第二次

他打得很快很模糊

但是我看得很清楚

那是 2147483647

但是！！！！！！！！！！

第二次，樓主的程式竟然顯示了

他不是質數！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

於是我學到了一課

原來整數，至少正整數具有神秘的性質

在整數論下，他同時是質數，又不是質數

這個結論很有趣，我的數學老師聽了也嚇了一大跳

我已經決定兩個月後發成國際論文

因為經過整數論的嚴密檢測了嘛，鐵定不會有錯的

希望樓主可以提供您的真實資料

我好把你的大名寫在我的paper上

感激不盡 m(_ _)m

目前測質數最快的方法是 Miller–Rabin 測試，連頓一下都不用。XD

/**********************************************************************************/
/*  Problem: a007 "判斷質數"                                                      */
/*  Language: C (1224 Bytes)                                                      */
/*  Result: AC(0.3s, 268KB) judge by this@ZeroJudge                               */
/*  Author: jdh8 at 2013-07-17 05:11:04                                           */
/**********************************************************************************/
#include <stdint.h>
#include <stdio.h>

uint32_t powmod (uint32_t base, uint32_t exp, uint32_t mod)
{
    uint32_t res = 1;
    base %= mod;
    while (exp) {
        if (exp % 2)
            res = res * (uint64_t)base % mod;
        exp /= 2;
        base = base * (uint64_t)base % mod;
    }
    return res;
}

int witnessLoop (uint32_t n, uint32_t s, uint32_t x)
{
    uint32_t r;

    if (x != 1 && x != n - 1) {
        for (r=1; r<s; ++r) {
            x = (uint64_t)x * x % n;
            if (x == n - 1)
                return 1;
        }
        return 0;
    }
    return 1;
}

int isPrime (uint32_t n)
{
    uint32_t d, s;
    
    switch (n) {
        case 0:
        case 1:
            return 0;
        case 2:
        case 7:
        case 61:
            return 1;
    }

    d = n - 1;
    s = 0;

    while (d % 2 == 0) {
        d /= 2;
        ++s;
    }

    return witnessLoop(n, s, powmod(2, d, n)) &&
           witnessLoop(n, s, powmod(7, d, n)) &&
           witnessLoop(n, s, powmod(61, d, n));
}

int main (void)
{
    uint32_t n;
    while (scanf("%u", &n) == 1)
        puts(isPrime(n) ? "質數" : "非質數");
    return 0;
}