📘 題目敘述
給你一個整數 n，如果 n 正好有三個正因數（divisors），回傳 true；否則回傳 false。
條件限制
1 <= n <= 10^4
🧠 解題思路（一）建立質數表
這題的關鍵性質是：
一個數字正好有三個正因數，當且僅當它是「某個質數的平方」。
原因是：如果 n = p^2，其中 p 是質數，那 n 的正因數只有 1, p, p^2 三個。反過來，如果 n 有三個正因數，那它一定是某個質數的平方。
所以我的做法就是你說的：先建立一份質數表，然後檢查 n 是不是其中某個質數的平方。
程式碼的流程是：
- 先用一個
check[]做簡單的篩法，找出 2~99 的質數 - 把所有質數放進
p - 掃過
p，只要n == p[l] * p[l]就回傳true - 都沒有就回傳
false
所有變數
p：存 2~99 的所有質數check：用來標記某個數是不是合數（被標記成 true 代表不是質數）
🪜 主要流程步驟
1. 先用 check[] 篩出 2~99 的質數
我把 check 初始化為全 false，代表一開始都先當成可能是質數。
接著我用兩層迴圈：
- 外層
i從 2 到 9 - 內層把
i的倍數（從2*i開始）全部標成true
這樣被標記過的數就不是質數。
2. 把沒被標記的數收集成質數表 p
我再掃一次 k = 2..99：
只要 check[k] == false，代表它沒有被任何小因數標記，是質數，就 push 進 p。
3. 檢查 n 是否為某個質數的平方
我掃 p 中所有質數：
只要 n == p[l] * p[l]，就代表 n 是質數平方，因此有且只有三個正因數，回傳 true。
4. 全部檢查完都不是，就回傳 false
如果沒有任何質數平方等於 n，代表 n 的因數數量不是 3，回傳 false。
⏱️ 複雜度
- 時間複雜度：
O(1)因為你只固定篩 2~99，再固定掃一小段質數表，規模是常數。 - 空間複雜度：
O(1)check[100]和質數表都固定大小。
💻 程式碼實作（一）
class Solution {
public:
bool isThree(int n) {
vector<int> p;
bool check[100] = {false};
for (int i = 2; i < 10; i++) {
for (int j = i * 2; j < 100; j += i) {
check[j] = true;
}
}
for (int k = 2; k < 100; k++) {
if (!check[k]) {
p.push_back(k);
}
}
for (int l = 0; l < p.size(); l++) {
if (n == p[l] * p[l]) {
return true;
}
}
return false;
}
};
🧠 解題思路（二）直接計算
我這份寫法就是最直接的做法：把 1..n 全部試一次，看有幾個數可以整除 n。
只要 n % i == 0，代表 i 是 n 的一個正因數，我就把 count++。
因為題目只在乎是不是「剛好 3 個」，所以我加了一個剪枝：一旦 count > 3，就不用再算了，直接回傳 false。
最後迴圈跑完後，如果 count == 3 就回傳 true，否則回傳 false。
所有變數
count：目前找到的因數數量
🪜 主要流程步驟
1. 初始化 count = 0
我用 count 記錄目前找到幾個因數，一開始當然是 0。
2. 從 1 掃到 n，遇到能整除就 count++
我用 i 從 1 到 n：
如果 n % i == 0，代表 i 是因數，就 count++。
3. 只要 count 超過 3，就直接回傳 false
因為題目要的是「剛好 3 個因數」：
一旦 count > 3，就不可能是答案了，直接回傳 false，省掉後面的檢查。
4. 掃完後判斷 count 是否等於 3
如果最後 count == 3，回傳 true；否則回傳 false。
⏱️ 複雜度
- 時間複雜度：
O(n)最壞要掃到n，每次做一次取模判斷。 - 空間複雜度：
O(1)
💻 程式碼實作（二）
class Solution {
public:
bool isThree(int n) {
int count = 0;
for (int i = 1; i <= n; i++) {
if (n % i == 0) {
count++;
}
if (count > 3) {
return false;
}
}
if (count == 3) {
return true;
}
return false;
}
};
🔗 題目連結
https://leetcode.com/problems/three-divisors/