a007: 判斷質數

 1#include <bits/stdc++.h>
 2using namespace std;
 3
 4const int MAX = 46341+1;
 5int pTable[MAX], pL;
 6
 7int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
 8    int n;
 9    for (int p=2; p<MAX; p++)
10        if (!pTable[p])
11            for (int pp=p+p; pp<MAX; pp+=p)
12                pTable[pp] = 1;
13    for (int p=2; p<MAX; p++)
14        if (!pTable[p])
15            pTable[pL++] = p;
16    pTable[pL] = INT_MAX; // array terminator
17    while (cin >> n && n) {
18        int sqrtN = sqrt(n); bool isPrime = (n != 1);
19        for (int i=0; pTable[i]<=sqrtN && isPrime; i++)
20            if (n % pTable[i] == 0)
21                isPrime = false;
22        if (isPrime) cout << "質數\n";
23        else cout << "非質數\n";
24    }
25    return 0;
26}