【基础算法】试除法判定质数(优化)

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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。