题解：P10720 [GESP202406 五级] 小杨的幸运数字

lailai0916 · 2024-07-09 14:41:32 · 题解

解题思路

循环遍历 [2,\sqrt{a}] 之间的整数 i，检查 i 是否是 a 的因子。如果是，就不断从 a 中去除 i 因子，直到 a 不能被 i 整除为止。

显然 a 最多有 1 个质因子大于 \sqrt{a}。循环结束后，如果 a>1，那么此时 a 也是一个质因子。

统计质因子的种数，判断其是否等于 2。时间复杂度为 O(n\sqrt{a})。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    while(n--)
    {
        int a;
        cin>>a;
        int cnt=0,t=a;
        for(int i=2;i*i<=t;i++)
        {
            if(a%i==0)
            {
                cnt++;
                while(a%i==0)a/=i;
            }
        }
        if(a>1)cnt++;
        cout<<(cnt==2)<<'\n';
    }
    return 0;
}