更新历程:
$2022.3.31$
写好题解
感谢@该用户被封禁、@Foraino0267和@whale77教冰中月如何打出$2^{31}$$2022.4.1$ 更新$sqrt$的含义
$2022.4.5$ 感谢@xiuzhiyuan指出键盘误,已改正
$2022.7.2$ 回来复习了一下,重新看了一下,发现键盘误好多,已全部改正,并且加了一些东西hh
$2023.1.29$ 改了一些奇怪的地方,然后加了一些证明
$2023.8.31$ 更改了错误的时间复杂度…
题目描述
给定 $n$ 个正整数 $a_i$,判定每个数是否是质数。
输入格式
第一行包含整数 $n$。
接下来 $n$ 行,每行包含一个正整数 $a_i$。
输出格式
共 $n$ 行,其中第 $i$ 行输出第 $i$ 个正整数 $a_i$ 是否为质数,是则输出 $Yes$,否则输出 $No$。
数据范围
$1≤n≤100$,
$1 ≤ ai ≤ 2^{31} −1$
输入样例:
2
2
6
输出样例:
Yes
No
算法1
(试除法) $O(\sqrt{n})$
这道题挺水的,但是不加优化不能过
判断是否是质数的函数很好写,一下是我写的一个没加优化的一个代码:
bool is_prime(int n){
if(n < 2) return false; //2是最小的质数,如果n小于2,那n肯定就不是质数
for(int i = 2;i < n;i ++){ //这个很好理解,从最小的质数2开始枚举到n - 1
if(n % i == 0){ //如果可以被i整除,说明这个数不是质数
return false; //返回不是
}
}
return true; //返回是
}
这个显然是不可以过的(亲测)
那又什么办法优化吗
有的
下面是Y总举出的所有不推荐的方法(逃
一、使用$sqrt$(根号)
为什么可以用根号呢
我们现在要证明:$n$的因数只需从$2$枚举到$\sqrt{(n)}$
如图
bool is_prime(int n){
if(n < 2) return false; //2是最小的质数,如果n小于2,那n肯定就不是质数
for(int i = 2;i <= sqrt(n);i ++){ //优化部分
if(n % i == 0){ //如果可以被i整除,说明这个数不是质数
return false; //返回不是
}
}
return true; //返回是
}
这个为什么不推荐呢¿
因为,$sqrt$这个函数运行很慢,每次执行时都要运算一遍,所以比较慢
但是这里竟然过了,离谱....
那我们这个算法也可以不用每次都算一遍$sqrt$,我们可以定义一个变量来存
看代码:
bool is_prime(int n){
if(n < 2) return false; //2是最小的质数,如果n小于2,那n肯定就不是质数
int x = sqrt(n);
for(int i = 2;i <= x;i ++){ //优化部分
if(n % i == 0){ //如果可以被i整除,说明这个数不是质数
return false; //返回不是
}
}
return true; //返回是
}
也过了,就离谱
如果你要使用这种方法,请注意:
必须判断$n$是否小于$2$,当然每种方法都需要判断
一定是$i ≤ sqrt(n)$,要不然你也会像我一样死得很惨
最后如果这个数经历了重重考验,一定要记得返回$true$(当然所有方法都需要)
如果不返回的话,也是可以的,但是,写上是个好习惯
二、$i * i ≤ n$
代码:
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
bool is_prime(int n){
if(n < 2) return false;
for(int i = 2;i * i <= n;i ++){ //这和用根号差不多吧...
if(n % i == 0){
return false;
}
}
return true;
}
int main(){
int n;
scanf("%d",&n);
for(int i = 1;i <= n;i ++){
int x;
scanf("%d",&x);
if(is_prime(x)) printf("Yes\n");
else printf("No\n");
}
return 0;
}
这么做也不推荐(逃
为什么呢
因为,说亿点人话,当$i$的值即将超过$int$的范围时,你再给它个$^2$,找死吧,很容易溢出
而且你犯得第二个错误是,你低估了数据
如果你要使用这种方法,请注意:
必须判断$n$是否小于$2$,当然每种方法都需要判断
最后如果这个数经历了重重考验,一定要记得返回$true$(当然所有方法都需要)
如果不返回的话,也是可以的,但是,写上是个好习惯
当然,这个代码过不了这道题,注意事项瞟一眼就行了
好了,这下是Y总推荐的模板了
三、$i ≤ n / i$
代码:
bool is_prime(int n){
if(n < 2) return false;
for(int i = 2;i <= n / i;i ++){ //优化内容
if(n % i == 0){
return false;
}
}
return true;
}
用的也是根号的原理,但这样就不会超时啦~
时间复杂度
参考文献
完整$C++$ 代码
#include <iostream>
#include <algorithm>
using namespace std;
bool is_prime(int n){
if(n < 2) return false;
for(int i = 2;i <= n / i;i ++){
if(n % i == 0){
return false;
}
}
return true;
}
int main(){
int n;
scanf("%d",&n);
for(int i = 1;i <= n;i ++){
int x;
scanf("%d",&x);
if(is_prime(x)) printf("Yes\n");
else printf("No\n");
}
return 0;
}
必须判断$n$是否小于$2$,当然每种方法都需要判断
在循环中$i ≤ n / i$一定要是$≤$,不然…嘿嘿嘿(逃
最后如果这个数经历了重重考验,一定要记得返回$true$(当然所有方法都需要)
如果不返回的话,也是可以的,但是,写上是个好习惯
使用i * i<=n时,问题应该是如果n趋近于int型的最大值,当i满足i * i<=n时,循环没有问题,但一旦到循环的最后一步,必然有ii>n,此时i * i就可能溢出。而如果使用i<=n/i,如果不满足条件,也就是i>n/i时,两边都不会溢出。
为啥i*i溢出会导致i溢出标称负数啊?
溢出我题解说了,就是当 $i$ 即将超过 $int$ 的范围的时候再去平方就会超过 $int$ 范围从而溢出。
而变为负数跟计算机存储机制(具体说是补码)有关,存储负数是用二进制最高位作为负号标记,如果最
高位是 $1$ 就会是负数,那有可能进位到最高位改成了 $1$,从而出现负数。但需要注意的是,如果移除后的数不是负数,这个数也是错的。
当然你只要了解到数据会溢出即可,不需要考虑为什么变成负数
好的好的,xxdl,我想岔了,以为是i溢出了
哥们为什么不能直接用n % i != 0就知到他不是质数了呀,为什么就是要先看他是不是约数呢
那你这样时间复杂度还是O(n),试除法是为了把时间复杂度优化到O($\sqrt{n}$)
谢了哥们
可以把 i * i <= x改成1ll * i * i <= x,即左边乘以long long类型的1,强制类型转换成long long类型
嗯嗯对的,但我们这里用 $int$ 就可以了啊。
你可以把$sqrt(n)$换成$\sqrt{n}$
代码
嗯,换了
不用谢如果用 i ∗ i ≤ n 这个条件,不满足条件不就退出循环了吗,有什么问题吗(请问溢出是什么概念)
不是不满足条件,溢出就是说超出变量类型范围(如int,long long等变量),然后会导致该变量无法存储,导致所谓溢出(一般会变为负数或出错),说直白点就是不够存了。
谢谢
怎么样才能打出这种炫酷的字体(指带横线
啊?
就是划掉的那种字体吗字旁边加上
~~
,两边都要加。如:
~~哈哈哈~~
效果:
哈哈哈其他字体你也可以参考抽风大佬的这篇分享
还真是thank u sir
$\sqrt{n}$
现在时间复杂度的错误改掉啦
感谢提醒
为什么定义一个变量存储sqrt(x)的值,回比直接将sqrt放进循环里所需运行时间会更多啊。
sqrt放进循环里每次都要算一次,用变量存储相当于预处理了,每次不必计算一次
请问第三种的时间复杂度是多少啊
$O(log \ n)$
吧,应该
谢谢
是$\sqrt{n}$
不一样吗,可能是我太弱了
不一样的!!!!
$\log n$是对数函数
$\sqrt{n}$是开根号!!!!
哦,
我是傻逼az,我是菜b话说第三个那个思路打错了吧?应该是n/i。而且根据本人自测,不一定要返回true。
因为bool函数默认返回就是true(狂逃bool函数默认返回true吗,我啥我记得我没返回true错了呢
哦,是的,谢谢纠正
键盘误了
额,
你听我狡辩,不不不是听我解释,不管要不要返回true,但是写上总是好的对此打呼:啊这。。。啊这。。。啊这。。。。。
额,所以你说我改还是不改呢
光顾着会消息了,奶茶都滴电脑上了啊这。。。(你听我狡辩,不不不是听我解释,不管奶茶滴上电脑的概率有多小,总是一个危险动作。不要放在电脑旁边的好。
其实都可以吧。
额,滴在边边上
(就是改还是不改)
听我狡辩那是多早年前的梗了,我故去的后桌还在用
然后我就蛮说了一下
我后桌抓米杰的死因:在做核酸的时候被冰中月踹死
那我就不改了(光速逃《危险动作》
?本人为哈没找到“抓米杰”其人?
他不在ACWing
他能会C艹???不可能
我全校只有3个人会C++(包括我)
《全校》
啊对对对
你不用怀疑,相信我就对了(光速逃所以说我太聪明了(狂逃那么多!!?
额,你是说你学校只有你一个会C++吗
好像是的
我也是