PAT乙級——1013（素數操作）

題目：數素數 （20 分）

令 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;

public class Main {
    public static void main(String []args){
        Scanner in = new Scanner(System.in);
        int head =in.nextInt();
        int bottom =in.nextInt();
        int temp[]=new int[1000];
        int k=0;
        int count=0;
        //素數定義從2開始計算
        for(int i=2;;i++){
            if(isPrime_3(i)==1){
                count++;
                if(count>=head&&count<=bottom){
                    temp[k]=i;
                    k++;
                }else if(count>bottom)
                    break;
            }
        }
        int j=1;
        for(int i=0;i<k;i++){
            if(j!=10){
                if (j!=1)
                    System.out.print(" ");
                System.out.print(temp[i]);
                j++;
            }else {
                System.out.println(" "+temp[i]);
                j=1;
            }
        }
    }

    //判斷是不是素數
    static int isPrime_3(int num)
    {
        //兩個較小數另外處理
        if(num ==2|| num==3 )
            return 1 ;
        //不在6的倍數兩側的一定不是質數
        if(num %6!= 1&&num %6!= 5)
            return 0 ;
        double tmp =Math.sqrt(num);
        //在6的倍數兩側的也可能不是質數
        for(int i= 5;i <=tmp; i+=6 )
            if(num %i== 0||num %(i+ 2)==0 )
                return 0 ;
        //排除所有，剩餘的是質數
        return 1 ;
    }
}
                

找了好久，調整輸入資料的長度，當是10的時候，發現輸出多空了一行

對比會發現退出标志前面多空了一行，問題定位到當最後一行是完整的10個數時，不能執行換行操作。

import java.util.Scanner;

public class Main {
    public static void main(String []args){
        Scanner in = new Scanner(System.in);
        int head =in.nextInt();
        int bottom =in.nextInt();
        int temp[]=new int[1000];
        int k=0;
        int count=0;
        //素數定義從2開始計算
        for(int i=2;;i++){
            if(isPrime_3(i)==1){
                count++;
                if(count>=head&&count<=bottom){
                    temp[k]=i;
                    k++;
                }else if(count>bottom)
                    break;
            }
        }
        int j=1;
        for(int i=0;i<k;i++){
            if(j!=10){
                if (j!=1)
                    System.out.print(" ");
                System.out.print(temp[i]);
                j++;
                //當收尾相遇時既不用換行
            }else if(j==10&&bottom==head)
                System.out.print(" "+temp[i]);
            else {
                System.out.println(" "+temp[i]);
                j=1;
            }
            head++;
        }
    }

    //判斷是不是素數
    static int isPrime_3(int num)
    {
        //兩個較小數另外處理
        if(num ==2|| num==3 )
            return 1 ;
        //不在6的倍數兩側的一定不是質數
        if(num %6!= 1&&num %6!= 5)
            return 0 ;
        double tmp =Math.sqrt(num);
        //在6的倍數兩側的也可能不是質數
        for(int i= 5;i <=tmp; i+=6 )
            if(num %i== 0||num %(i+ 2)==0 )
                return 0 ;
        //排除所有，剩餘的是質數
        return 1 ;
    }
}
                

emmmmmmm，不過呢存在一個

運作逾時

的問題，我運作了

三次，兩次逾時18分，一次AC

。送出不成功可以多送出兩下試試。親測對java沒有那麼友好。