【基础算法】试除法判定质数(优化)
2023-12-17 23:54:41
算法优化模板
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;
}
注意这里的一个总要优化是for循环的终止条件是i<=n/i。为什么不是i<=n或者i<=根号n呢?以为i<=n太慢了原始解法,而i<=根号n的话,其实和这里的优化是类似的,但是计算机底层在执行根号的时候会比较慢。那具体为什么i<=n/i可以呢?想不通的建议找几个例子试试就知道了,严格证明也不复杂。
必须判断nn是否小于2,当然每种方法都需要判断!!
一定是i≤sqrt(n),要不然你也会像我一样死得很惨
最后如果这个数经历了重重考验,一定要记得返回truetrue(当然所有方法都需要)
如果不返回的话,也是可以的
题目
代码实现
import java.io.*;
public class Main {
static int n;
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
n = Integer.parseInt(reader.readLine());
while (n-- > 0) {
int a = Integer.parseInt(reader.readLine());
if (is_prime(a)) {
writer.write("Yes\n");
} else {
writer.write("No\n");
}
}
writer.flush();
writer.close();
reader.close();
}
public static boolean is_prime(int n) {
if (n < 2) return false;
for (int i = 2; i <= n / i; i++) {//推荐这种写法,而不是i * i <= n 或者i <= sqrt(n)
if (n % i == 0) {
return false;
}
}
return true;
}
}
文章来源:https://blog.csdn.net/qq_45858191/article/details/135051949
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!