自动搬运

查看原文

来自洛谷，原作者为

	PokerKing IAKIOI

搬运于2025-08-24 23:00:36，当前版本为作者最后更新于2024-07-09 14:36:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

如果一个数的质因子中只有两个不同的数则输出 $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;
}