使用java判断质数的三种方法

￡神魔★判官ぃ 2024-03-27 09:01 121阅读 0赞

> 方法一：质数只能被1和它本身整除

import java.util.Scanner;
    
    public class Test {
        public static void main(String[] args) {
            int n = new Scanner(System.in).nextInt();
            int i = 2;
            for (;i < n;i++){
                if (n % i == 0){
                    System.out.println(n + "不是素数");
                    break;
                }
            }
            //将2~（n-1）之间所有整数都除一遍，以确保其中没有可以整除的数
            if (i == n){
                System.out.println(n + "是素数");
            }
        }
    }

> 方法二：一个数总能写成“n = a \* b”的形式，a和b之间一定有一个数不大于n/2

import java.util.Scanner;
    
    public class Test {
        public static void main(String[] args) {
            int n = new Scanner(System.in).nextInt();
            int i = 2;
            for (;i < n/2;i++){
                if (n % i == 0){
                    System.out.println(n + "不是素数");
                    break;
                }
            }
            //将2~（n/2）之间所有整数都除一遍，以确保其中没有可以整除的数
            //每一个整数都可以看做有两个数相乘得到，且每一个整数不会超过原整数的一半，除了原整数本身
            if (i > n/2){
                System.out.println(n + "是素数");
            }
        }
    }

> 方法三：每一个整数都可以看做由两个数相乘得到，且每个乘数不大于原整数的平方根

import java.util.Scanner;
    
    public class Test {
        public static void main(String[] args) {
            int n = new Scanner(System.in).nextInt();
            int i = 2;
            for (;i <= Math.sqrt(n);i++){
                if (n % i == 0){
                    System.out.println(n + "不是素数");
                    break;
                }
            }
            if (i > Math.sqrt(n)){
                System.out.println(n + "是素数");
            }
        }
    }