题意整理。

• 输入两个正整数。
• 输出这两个正整数之间，有多少个素数。

方法一（循环）

1.解题思路

• 首先比较start和end大小，如果start比end大，则交换start和end的值。
• 然后遍历start到end之间所有的数，如果大于2，并且是素数，则计数加1。
• 关于如何判断一个数是否是素数，只需看这个数i能否被2到根号i之间的任意一个数整除，如果能，则不是素数，否则是素数。

动图展示（判断是否是素数）：

2.代码实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int start = scanner.nextInt();
        int end = scanner.nextInt();
        method(start,end);

    }
    public static void method(int start,int end){
        int count=0;

        //如果start大于end，则交换两者的值
        if(start>end){
            int temp=start;
            start=end;
            end=temp;
        }
        //遍历start到end之间所有的数
        for(int i=start;i<=end;i++){
            //如果大于2，并且是素数，则计数加1
            if(i>2&&isPrime(i)){
                count++;
            }
        }

        System.out.println(start+"到"+end+"之间有"+count+"个大于2的素数");

    }
    
    //判断是否是素数
    private static boolean isPrime(int x){
        for(int i=2;i*i<=x;i++){
            //只要能被i整除，则不是素数
            if(x%i==0){
                return false;
            }
        }
        return true;
    }
}

3.复杂度分析

• 时间复杂度：判断一个数是否为素数，最多执行$\sqrt{i}\backslash sqrt\{i\}$次循环，所以从start到end的范围内，需要执行${\sum }_{i=start}^{end}\sqrt{i}\backslash sum\_\{i=start\}^\{end\}\; \backslash sqrt\{i\}$次循环，${\sum }_{i=1}^n\sqrt{i}\backslash sum\_\{i=1\}^\{n\}\; \backslash sqrt\{i\}$的值为$2\mathrm{/}3\ast n^{3\mathrm{/}2}2/3*n^\{3/2\}$，所以${\sum }_{i=start}^{end}\sqrt{i}\backslash sum\_\{i=start\}^\{end\}\; \backslash sqrt\{i\}$的值为$2\mathrm{/}3\ast (en{d}^{3\mathrm{/}2}-star{t}^{3\mathrm{/}2})2/3*(end^\{3/2\}-start^\{3/2\})$，所以时间复杂度为$O(n^{3\mathrm{/}2})O(n^\{3/2\})$。
• 空间复杂度：不需要额外的空间，所以空间复杂度为$O(1)O(1)$。