质数判定

✅ 概念

素数（Prime Number）是指大于 $1$ 的自然数中，除了 $1$ 和它本身以外不再有其他约数的整数。

---

🔍 素数判定

🔹 基本思想

朴素方法的核心在于枚举 $2 \sim n-1$ 之间的所有整数：

• 若存在 $i$ 满足 $i \mid n$（即 $n$ 能被 $i$ 整除），说明 $n$ 不是素数。

为了优化效率：

• 设 $n = a \times b$，其中 $a \leq b$，可知 $a \leq \sqrt{n}$。
• 因此只需判断 $[2, \sqrt{n}]$ 范围内是否有能整除 $n$ 的数。

🔹 实现代码

bool is_prime(int n) 
{
    if (n < 2) return false; // 0 和 1 不是素数
    for (int i = 2; i * i <= n; i++) // 注意 i * i 是否爆 int
    {
        if (n % i == 0)
            return false;
    }
    return true;
}

💡 补充说明

• 判断是否是质数的时间复杂度为 $O(\sqrt{n})$。
• 注意边界情况时要特别处理。

---

🔧 枚举因子

与素数判断类似，也可以在 $O(\sqrt{n})$ 时间内找出所有因子：

🔹 vector 实现代码

vector<int> get(int n) 
{
    vector<int> fact;
    for (int i = 1; i * i <= n; i++) 
    {
        if (n % i == 0) 
        {
            fact.push_back(i);
            if (i != n / i) // 避免重复，例如 36 = 6 * 6
                fact.push_back(n / i);
        }
    }
    sort(fact.begin(), fact.end());
    return fact;
}

🔹 数组实现代码

int fact[N], cnt, q, x;
void get(int n) 
{
    cnt = 0;
    for (int i = 1; i * i <= n; i++) 
    {
        if (n % i == 0) 
        {
            fact[++cnt] = i;
            if (i != n / i) // 避免重复，例如 36 = 6 * 6
            {
                fact[++cnt] = n / i;
            }
        }
    }
    sort(fact + 1, fact + cnt + 1);
}
int main()
{
    cin >> q;
    while (q--)
    {
        cin >> x;
        get(x);
        for (int i = 1; i <= cnt; i++) 
            cout << fact[i] << " ";
        cout << "\n";
    } 
}

📌 示例

输入：n = 36 输出：1 2 3 4 6 9 12 18 36

---

📘 小结

操作	方法	时间复杂度
判定是否质数	枚举 $\sqrt{n}$ 范围	$O(\sqrt{n})$
枚举因子	同上	$O(\sqrt{n})$

---