A3139 | 质因
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
时间限制:1000ms
空间限制:256mb
在数学当中，我们可以发现一个非1的正整数可以由许多质因子所组成，许多线性的质数筛选算法也是基于这个性质所得。
现在，$Yuilice$给予你一个正整数$x$，假若在范围当中$[1,x]$的质数数量超出$\lfloor\frac{x}{2}\rfloor$，那么请输出
YES,反之输出NO。注:本题包含多组测试样例
输入格式
第一行输入一个整数$t(1 \leq t \leq 10^4)$ - 代表共有T组样例进行测试。
第二行输入一个整数$x(2 \leq x \leq 10^{18})$ - 代表Yuilice给予你的数字。
第二行输入一个整数$x(2 \leq x \leq 10^{18})$ - 代表Yuilice给予你的数字。
输出格式
针对于每组样例 - 输出
YES或NO，独占一行。输入输出样例
输入 #1
3 2 3 4
输出 #1
NO YES NO
【样例解释】
1. 2的质数数量为1，不超过$\lfloor \frac{2}{2} \rfloor = 1$。
2. 3的质数数量为2,分别为$[2,3]$,超过了$\lfloor \frac{3}{2} \rfloor = 1$。
3. 4的质数数量为2,分别为$[2,3]$,不超过$\lfloor \frac{4}{2} \rfloor = 2$。
- 1 ~ 5 的数据点数据满足 $t = 1 ,1 \leq x \leq 10^3$
- 6 ~ 10 的数据点数据满足 $1 \leq t \leq 10^3 , 1 \leq x \leq 10^9$
- 11 ~ 20 的数据点没有任何限制
1. 2的质数数量为1，不超过$\lfloor \frac{2}{2} \rfloor = 1$。
2. 3的质数数量为2,分别为$[2,3]$,超过了$\lfloor \frac{3}{2} \rfloor = 1$。
3. 4的质数数量为2,分别为$[2,3]$,不超过$\lfloor \frac{4}{2} \rfloor = 2$。
测试数据点
- 1 ~ 5 的数据点数据满足 $t = 1 ,1 \leq x \leq 10^3$
- 6 ~ 10 的数据点数据满足 $1 \leq t \leq 10^3 , 1 \leq x \leq 10^9$
- 11 ~ 20 的数据点没有任何限制
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？