alan23273850 的刷題筆記
a505: B. T-primes
Tags: prime-table
出處：https://zerojudge.tw/ShowProblem?problemid=a505
提交：https://zerojudge.tw/Submissions?problemid=a505&account=allllllan123456
問題：請你判斷多個不超過 $10^{14}$ 的正整數分別是否剛好有 3 個正因數。
解法：我們都知道一個正整數的正因數個數是標準分解式內每個質數所對應到的次方加一的乘積，那因為 3 不能被分解，我們便知道符合條件的數必定只能表達成一個質數的平方。於是我們可以先建質數表 (最大到 $10^7$)，分辨誰是質數誰不是質數，用 bitset 的話更省空間，接著再對每個數字開根號，如果剛好是整數又是質數的話便合乎條件。
1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAX = 10000001;
5
6int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
7 int T; cin >> T; 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 (T--) { long long n; cin >> n;
14 long long sqrtN = sqrt(n);
15 if (sqrtN*sqrtN==n && !isNotPrime[sqrtN])
16 cout << "YES\n";
17 else
18 cout << "NO\n";
19 }
20 return 0;
21}