简答题 偏难
#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。


输入样例

3
7
12
30

输出样例

0
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&lt;bits/stdc++.h&gt; using namespace std; map&lt;int,int&gt; mp; const int N = 1e5+10; int calc(int x) { int res = 0; set&lt;int&gt; s; for (int i = 2; i * i &lt;= 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&gt;&gt;n; long long ans = 0; int pre = 0; for(int i=1;i&lt;=n;i++){ cin&gt;&gt;a[i]; int x = calc(a[i]); if(x==2)cout&lt;&lt;"1\n"; else cout&lt;&lt;"0\n"; } }</pre>
解析

1.计算输入数据的质因子的个数。具体实现中,可以从最小的质数开始试除,统计不重复的质因子个数。

2.当质因子个数为2时,返回1表示是幸运数字,否则返回0。