A32250. 小杨的幸运数字题面描述小杨认为他的幸运数字应该恰好有两种不同的质因子，例如，12=2*2*3的质因子有 2,3，恰好为两种不同的质因子，因此12是幸运数字，而30=2*3*5的质因子有2,3,5，不符合要求，不为幸运数字。小杨现在有n个正整数，他想知道每个正整数是否是他的幸运数字。
填空题
困难
知识点
题目描述
小杨的幸运数字
题面描述
小杨认为他的幸运数字应该恰好有两种不同的质因子，例如，12=2*2*3的质因子有 2,3，恰好为两种不同的质因子，因此12是幸运数字，而30=2*3*5的质因子有2,3,5，不符合要求，不为幸运数字。
小杨现在有n个正整数，他想知道每个正整数是否是他的幸运数字。
输入格式
第一行包含一个正整数 n，代表正整数个数。
之后 n 行，每行一个正整数。
输出格式
输出 n 行，对于每个正整数，如果是幸运数字，输出1 ，否则输出0 。
样例1
输入
3
7
12
30
输出
0
1
0
样例解释
7的质因子有7，只有一种。
12的质因子有2，3，恰好有两种。
30的质因子有2，3，5，有三种。
数据范围
对于全部数据，保证有1 ≤ n ≤10000，每个正整数 ai 满足2 ≤ ai ≤ 1000000
参考答案
#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) {
1 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";
}
}
上一题
下一题