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

· · 题解

题意

如果一个数的质因子中只有两个不同的数则输出 1，否则输出 0。

思路

从第一个质因子遍历到 sum 的话很明显是 O(nt) 最大是 n^{10} 很明显会炸掉。

所以遍历到 sum 是不行的，考虑正整数 n 最大的质因数是 \sqrt{n} 所以遍历到 \sqrt{n} 即可。

代码

#include <bits/stdc++.h>
using namespace std;
int lucky(int sum) {//函数处理是否为幸运数 
    int ans=0;
    int a=sum;
    for(int i=2; i*i<=a; i++) {
        if(sum%i==0) {
            ans++;
            while(sum%i==0) {
                sum/=i;
            }
        }

    }
    if(sum>1) {
        ans++;
    }
    if(ans==2) {
        return 1;
    } else {
        return 0;
    }
}
int main() {
    int n;
    cin>>n;
    int a;
    while(n--) {
        scanf("%d",&a);
        cout<<lucky(a)<<endl;
    }
    return 0;
}