方案一（未优化）

大多数可能想到的是以下这种方法

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 + "是素数!");
        }
        else{
            System.out.println(input + "不是素数!");
        }
    }
}

分析：

        要除2 ~ (n - 1)个数字，效率太低，面试官肯定不满意（doge）

---

方案二（初阶优化）

有一点经验的可能会想到这里

    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 + "是素数!");
        }
        else{
            System.out.println(input + "不是素数!");
        }
    }

分析：

        例如16这个数，可以写成1*16、2*8、4*4，仔细观察每组数中都至少有一个数小于或等于n/2，所以只需要去除2 ~ n/2之间的数即可，减少了将近一半的计算量，这时，面试官可能还会说：小伙子不错，还能再优化一下吗？

---

方案三（进阶优化）

有些经验的人可能就会想到了

    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 + "是素数!");
        } else {
            System.out.println(input + "不是素数!");
        }
    }

分析：

        例如16可以写成1*16、2*8、4*4，仔细观察，每组数据中至少有一个数是小于或等于根号16，所以计算量又可以减小到2~根号16，面试官可能会说：好~小伙子，进我们公司吧！