alan23273850 的刷題筆記
d705: 判断质数（二）
Tags: prime-table
出處：https://zerojudge.tw/ShowProblem?problemid=d705
提交：https://zerojudge.tw/Submissions?problemid=d705&account=allllllan123456
問題：判斷多個 int 範圍內的正整數是否為質數。
解法：這題是 d709 的進階版，因為 $2^{31}-1$ 的表格實在建不下，而且就算記憶體足夠建得出整張表格也會超時，那這題比較建議的作法便是只建一部份 $(約到\ \sqrt{2^{31}-1}\approx46341)$ 的表格，則對於每個大於 $1$ 的整數 $n$，只要它能被 $2$ 到 $\sqrt n$ 之間的任何一個質數 $p$ 整除，$n$ 就是合數，否則就是質數，至於 $n=1$ 的情況則要另外處理。
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 << "0\n";
23 else cout << "1\n";
24 }
25 return 0;
26}