PAT 乙级 1013 数素数 (20 分) java

令 P**i 表示第 i 个素数。现任给两个正整数 M≤N≤10的4次方，请输出 P**M 到 P**N 的所有素数。

输入格式：

输入在一行中给出 M 和 N，其间以空格分隔。

输出格式：

输出从 P**M 到 P**N 的所有素数，每 10 个数字占 1 行，其间以空格分隔，但行末不得有多余空格。

输入样例：

5 27

输出样例：

11 13 17 19 23 29 31 37 41 43
47 53 59 61 67 71 73 79 83 89
97 101 103

代码：

import java.util.Scanner;
import static java.lang.StrictMath.sqrt;

public class Main{
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int []su=new int[m];
        boolean b=true;
        int c=0,s=1;
        su[0]=2;
        //找素数存到数组中
        for (int i = 3; s <m ; i++) {
            b=true;
            //缩短找到素数的时间的关键，开根号
            int i_sqrt = (int)sqrt(i);
            for (int j = 2; j <=i_sqrt ; j++) {
                if (i%j==0){
                    b=false;
                    break;
                }
            }
            if (b){
                su[s]=i;
                s++;
            }
        }
        //输出
        int ic=0;
        for (int i = n-1; i <m ; i++) {
            if (ic%10==0){
                System.out.print(su[i]);
            }else  if (ic%10==9){
                System.out.println(" " + su[i]);
            }else {
                System.out.print(" " + su[i]);
            }
            ic++;
        }
    }
}

思路：

1.创建一个长度为m的数组

2.检验为素数放入素数数组中

3.按格式输出

思考：

1.重点是缩短找到素数的时间（因为本题有200ms的时间限制）

2.没将 j 层循环的循环范围给缩小到 i 的根号下的近似值，否则将一直超时。

下面说说这个根号下的近似值的原理：

问：有一个数N,要判断其是否为素数,只须检查N可否被2到根号N之间的数整除即可？
答：因为N=根号N根号N
如果N含有一个大于根号N,小于N的约数a,则N必含有一个大于1,小于根号N的约数b
使得N=ab
所以如果一个数N从2到根号N之间没有约数,则必然在根号N到N-1之间也没有约数,即N是一个素数

3.这题和1007素数对猜想有点相似，重点都是我上面的说的第二点，有兴趣的话可以看看我1007题怎么写的。

https://blog.csdn.net/weixin_42256997/article/details/102944466