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

原题链接

• 洛谷 P10720 [GESP202406 五级] 小杨的幸运数字

解题思路

循环遍历 $[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()
{
	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;
}