题目的主要信息：

• 输入一个大于1的数，判断其是否是质数

具体做法：

判断一个数$nn$n是否是质数，我们只需要找它有无因子即能否被整除即可。从2开始遍历到该数前一个数$n-1n-1$n−1，查看每个数能否整除$nn$n，如果可以整除即余数为0，则记录下不是质数，跳出循环，输出即可，如果检查完所有的数都没有因子，则它是质数。

其实我们不用遍历到$n-1n-1$n−1，遍历到$\sqrt{n}\backslash sqrt\; n$n​即可，因为$\sqrt{n}\backslash sqrt\; n$n​后面如果有因子，必定是乘上另一个小于$\sqrt{n}\backslash sqrt\; n$n​的数字，那我们前面就已经验证过了，因此以$\sqrt{n}\backslash sqrt\; n$n​为遍历终点就可以了。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        Scanner scan = new Scanner(System.in);
        int number = scan.nextInt();
        System.out.println(main.isPrimeNumber(number));
    }
    public Boolean isPrimeNumber(int number){
        for(int i = 2; i * i <= number; i++){
            if(number % i == 0) //能整除没有余数
                return false; //说明找到了因子，不是质数
        }
        return true; //遍历完都没找到因子
    }
}

复杂度分析：

• 时间复杂度：$O\left(\sqrt{n}\right)O(\backslash sqrt\; n)$O(n​)，从2遍历到$\sqrt{n}\backslash sqrt\; n$n​
• 空间复杂度：$O\left(1\right)O(1)$O(1)，无额外空间