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;
}