alan23273850 的刷題筆記
d709: 判断质数（一）
Tags: prime-table
出處：https://zerojudge.tw/ShowProblem?problemid=d709
提交：https://zerojudge.tw/Submissions?problemid=d709&account=allllllan123456
問題：判斷多個不超過 1000000 的正整數是否為質數。
解法：單純用 bitset 建質數表而已，基本款。
1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAX = 1000001;
5
6int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
7 int n; bitset<MAX> isNotPrime;
8 for (int p=2; p<MAX; p++)
9 if (!isNotPrime[p])
10 for (int pp=p+p; pp<MAX; pp+=p)
11 isNotPrime[pp] = true;
12 isNotPrime[1] = true; // corner cases
13 while (cin >> n && n)
14 cout << isNotPrime[n] << '\n';
15 return 0;
16}