题目的主要信息：

输入两个正整数，输出这两个正整数之间（左闭右闭）有多少大于2的素数
如果start>end，则将start设为end，end设为start

具体做法：

我们需要遍历start和end之间的所有数，查看其是否是素数，如果是素数则统计一次。因为两个数大小未知，因此我们要先比较其大小，如果start较大还需要交换二者的值。然后从start遍历到end，对每个数判断是否是素数即可。

判断一个数 $n$ 是否是素数，我们只需要找它有无因子即能否被整除即可。从2开始遍历到该数前一个数 $n - 1$ ，查看每个数能否整除 $n$ ，如果可以整除即余数为0，返回false，如果检查完所有的数都没有因子，则它是质数，返回true。

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

alt

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 boolean isPeime(int num){
        for(int i = 2; i * i <= num; i++){ //从2遍历到根号num
            if(num % i == 0) //一旦可以整除就不是素数
                return false;
        }
        return true;
    }
    public static void method(int start,int end){
        int count=0;
        if(start > end){ //如果start更大，则交换
            int temp = start;
            start = end;
            end = temp;
        }
        for(int i = start; i <= end; i++){ //遍历start到end
            if(i <= 2) //不大于2的不要
                continue;
            if(isPeime(i)) //判断这个数是否是素数
                count++; //返回true，素数+1
        }
        System.out.println(start+"到"+end+"之间有"+count+"个大于2的素数"); //输出
    }
}

复杂度分析：

时间复杂度： $O(n^{3/2})$ ，这里的 $n$ 是start到end之间的个数，查看 $n$ 是否是素数最多为 $\sqrt n$ ，因此这里是 $\sqrt 3 + ... + \sqrt n = 2/3*n^{3/2} -1 - \sqrt 2$ ，因此查看所有的isPrime函数需要 $O(n^{3/2})$
空间复杂度： $O (1)$ ，无额外空间使用

题解 | #判断素数个数#

题目的主要信息：

具体做法：

复杂度分析：