题意整理

• 输入一个大于1的整数。
• 判断是否是质数。

方法一（循环）

1.解题思路

• 定义一个boolean型变量，判断是否是质数。
• 使用一个循环进行判断，如果number能被2到number平方根的任意一个数整除，说明不是质数。

动图展示：

2.代码实现

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){
        //定义一个变量表示是否是质数
        boolean f=true;
        //如果number能被2到number平方根的任意一个数整除，说明不是质数
        for(int i=2;i*i<=number;i++){
            if(number%i==0){
                return false;
            }
        }
        return f;
    }
}

3.复杂度分析

• 时间复杂度：假设输入的数是n，最坏情况下，需要循环$n^{1\mathrm{/}2}n^\{1/2\}$次，所以时间复杂度为$O(n^{1\mathrm{/}2})O(n^\{1/2\})$。
• 空间复杂度：需要额外常数级别的空间，所以空间复杂度为$O(1)O(1)$。