Baidu classic interview question - determine prime (how to optimize?)

Catalog

Scheme 1 （ Not optimized ）

Option two （ Primary optimization ）

Option three （ Advanced optimization ）

---

Scheme 1 （ Not optimized ）

Most people may think of the following methods

public class Main(){
 
   public static void main11(String[] args){
        Scanner scanner = new Scanner(System.in);
        int input = scanner.nextInt();
        int i = 0;
        for(i = 2; i < input; i++){
            if(input % i == 0){
                break;
            }
        }
        if(i == input){
            System.out.println(input + " Prime number !");
        }
        else{
            System.out.println(input + " Not primes !");
        }
    }
}

analysis ：

        To divide 2 ~ (n - 1) A digital , Efficiency is too low , The interviewer must not be satisfied （doge）

---

Option two （ Primary optimization ）

Those with a little experience may think of this

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int input = scanner.nextInt();
        int i = 0;
        for(i = 2; i <= input/2; i++){
            if(input % i == 0){
                break;
            }
        }
        if(i > input/2){
            System.out.println(input + " Prime number !");
        }
        else{
            System.out.println(input + " Not primes !");
        }
    }

analysis ：

        for example 16 The number of , It can be written. 1*16、2*8、4*4, Carefully observe that at least one number in each group is less than or equal to n/2, So just remove 2 ~ n/2 The number between , It reduces the amount of calculation by nearly half , At this time , The interviewer may also say ： Nice guy , Can you optimize it again ？

---

Option three （ Advanced optimization ）

Some experienced people may think of

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int input = scanner.nextInt();
        int i = 0;
        for (i = 2; i <= Math.sqrt(input); i++) {
            if (input % i == 0) {
                break;
            }
        }
        if (i > Math.sqrt(input)) {
            System.out.println(input + " Prime number !");
        } else {
            System.out.println(input + " Not primes !");
        }
    }

analysis ：

        for example 16 It can be written. 1*16、2*8、4*4, Observe carefully , At least one number in each group of data is less than or equal to the root 16, So the amount of calculation can be reduced to 2~ Radical sign 16, The interviewer may say ： good ~ Young man , Join our company ！