时间限制: 1 s
空间限制: 16000 KB
题目等级 : 白银 Silver
题目描述 Description
在很久以前,在遥远的东方,有一个整数帝国,它里面里居住着大量的正整数,了缓解都城的住房压力,皇帝阿里斯丁想把一些“无用”的正整数迁到城外,但如何确定正整数是“无用”的呢?国王十分苦恼,夜不成眠。
聪明的宰相克鲁索提议,除了1以外的所有正整数,如果它能被表示为a*b的形式,而a和b也都是正整数的话,那么这个数就是“无用”的。比如:120可以表示为2×60的形式,因此120就是“无用”的;而13除了1×13外不存在其他a*b的形式,因此13就不是“无用”的。现在,只需要判断某个正整数n是否“无用”。
国王认为这个提议是极好的,因此把维护都城和平稳定的重任交给了你,因为你是整数帝国的首席信息安全专家。(这个太无厘头了点......)
你必须尽快处理,因为这是古代,失职是要被砍头的!
输入描述 Input Description
输入数据仅一行,包含一个正整数n。
输出描述 Output Description
输出数据仅一行,如果该数无用,输出“Yes!”
如果有用,输出“No!”
样例输入 Sample Input
120
样例输出 Sample Output
Yes!
数据范围及提示 Data Size & Hint
1<n<=1000000
a,b>1
水题——>素数判定
1 #include<iostream>
2 #include<cstdio>
3 #include<cmath>
4 using namespace std;
5 const int MAXN=10000001;
6 int vis[MAXN];
7 int main()
8 {
9 int n;
10 scanf("%d",&n);
11 for(int i=2;i<=sqrt(n);i++)
12 {
13 if(vis[i]==0)
14 {
15 for(int j=i*i;j<=n;j=j+i)
16 {
17 vis[j]=1;
18 }
19 }
20 }
21 if(vis[n]==0)
22 {
23 printf("No!");
24 }
25 else
26 {
27 printf("Yes!");
28 }
29 return 0;
30 }