2728 整数帝国问题

2728 整数帝国问题

时间限制: 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

分类标签 Tags 点此展开

水题——>素数判定

 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  } 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏HansBug's Lab

3409: [Usaco2009 Oct]Barn Echoes 牛棚回声

3409: [Usaco2009 Oct]Barn Echoes 牛棚回声 Time Limit: 3 Sec  Memory Limit: 128 MB Su...

2527
来自专栏测试开发架构之路

C语言之位运算

指针和位运算很适合编写系统软件的需要。 位运算指进行二进制位的运算。   按位与”运算符 & 用途 1)清零 2)取一个数中某些指定位(比如只需要低8位) 3)...

46010
来自专栏HansBug's Lab

2431: [HAOI2009]逆序对数列

2431: [HAOI2009]逆序对数列 Time Limit: 5 Sec  Memory Limit: 128 MB Submit: 954  Solv...

2936
来自专栏wannshan(javaer,RPC)

dubbo序列化过程源码分析

先看下dubbo在serialize层的类设计方案 序列化方案的入口,是接口Serialization的实现类。 /** * Serialization. ...

8829
来自专栏码匠的流水账

java10系列(二)Local-Variable Type Inference

本文主要解读下java10的Local-Variable Type Inference

1671
来自专栏草根专栏

用C#(.NET Core) 实现简单工厂和工厂方法设计模式

本文源自深入浅出设计模式. 只不过我是使用C#/.NET Core实现的例子. 前言 当你看见new这个关键字的时候, 就应该想到它是具体的实现. ? 这就是一...

8324
来自专栏码匠的流水账

聊聊storm WindowTridentProcessor的FreshCollector

本文主要研究一下storm WindowTridentProcessor的FreshCollector

883
来自专栏SeanCheney的专栏

《Pandas Cookbook》第01章 Pandas基础

公司网址,http://www.dunderdata.com(dunder是蒸馏朗姆酒的残留液体,取这个名字是类比数据分析过程) GitHub地址:https...

1622
来自专栏java达人

数字的陷阱

Java中对数字的处理,如四舍五入,如加减乘除,貌似是一个很基础很简单的知识点,但是如果你没有对他进行充分了解,很容易掉进它的陷阱里。 1、浮点数运算 先来看一...

1938
来自专栏一个会写诗的程序员的博客

从爬取的文章 HTML 中提取出中文关键字

https://github.com/KotlinSpringBoot/saber

2806

扫码关注云+社区

领取腾讯云代金券