简答题
偏难
#21132
小杨的幸运数字 时间限制:1.0 s 内存限制:512.0 MB 题面描述 小杨认为他的幸运数字应该恰好有两种不同的质因子,例如,12=2×2×3 的质因子有2…
小杨的幸运数字
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨认为他的幸运数字应该恰好有两种不同的质因子,例如,12=2×2×3 的质因子有2,3,恰好为两种不同的质因子,因此12是幸运数字,而30=2×3×5 的质因子有2,3,5,不符合要求,不为幸运数字。
小杨现在有n个正整数,他想知道每个正整数是否是他的幸运数字。
输入格式
第一行包含一个正整数n,代表正整数个数。
之后n行,每行一个正整数。
输出格式
输出n行,对于每个正整数,如果是幸运数字,输出1,否则输出0。
输入样例
输出样例
样例解释
7的质因子有7,只有一种。
12的质因子有2,3,恰好有两种。
30的质因子有2,3,5,有三种。
数据范围

对于全部数据,保证有1≤n≤104,每个正整数ai满足2≤ai≤106。
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include<bits/stdc++.h>
using namespace std;
map<int,int> mp;
const int N = 1e5+10;
int calc(int x) {
int res = 0;
set<int> s;
for (int i = 2; i * i <= x; i++) {
if (x % i == 0) {
s.insert(i);
while (x% i == 0){
x/= i;
}
}
}
if (x != 1) {
s.insert(x);
}
return (int)s.size();
}
int a[N];
int main(){
int n;
cin>>n;
long long ans = 0;
int pre = 0;
for(int i=1;i<=n;i++){
cin>>a[i];
int x = calc(a[i]);
if(x==2)cout<<"1\n";
else cout<<"0\n";
}
}</pre>
解析
1.计算输入数据的质因子的个数。具体实现中,可以从最小的质数开始试除,统计不重复的质因子个数。
2.当质因子个数为2时,返回1表示是幸运数字,否则返回0。