一道PAT1059 C语言竞赛 运行超时

Question

思路是每次查询都尝试遍历ID数组，分类讨论，操作结束break出去。但是最终两个超时

代码如下：

import java.util.*;
public class Main {

    public static boolean isPrime(int n){
        int count=0;
        for(int i=2;i<=Math.sqrt(n);i++){
            if(n%i==0){
                count++;
                break;
            }
        }
        if(count==1) return false;
        else return true;
    }
    
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);

        int N=Integer.parseInt(scan.nextLine());
        String[] id=new String[N+1];
        for(int i=1;i<=N;i++){
            id[i]=scan.nextLine();
        }

        boolean[] checked=new boolean[N+1];
        Arrays.fill(checked,false);

        int query=Integer.parseInt(scan.next());

        for(int i=1;i<=query;i++){
            String ID=scan.next();
            for(int j=1;j<=N;j++){
                if(id[j].equals(ID)&&!checked[j]){
                    if(j==1) System.out.println(ID+":"+" Mystery Award");
                    else if(isPrime(j)) System.out.println(ID+":"+" Minion");
                    else System.out.println(ID+":"+" Chocolate");
                    checked[j]=true;
                    break;
                }
                else if(id[j].equals(ID)&&checked[j]) {
                    System.out.println(ID+": Checked");
                    break;
                }

                if(j==N) System.out.println(ID+": Are you kidding?");
            }

        }

    }
}

我一开始想用BufferedReader来读取的，但是readline()读取不了末行 只能用效率很低的Scanner，请问有没有什么解决办法？

Answer 1

有好几个可以优化的地方
isPrime方法，可以不用变量，而且把算术平方根结果保存起来，防止重复计算，改成这样：

 public static boolean isPrime(int n){
        int temp=(int)Math.sqrt(n);
        for(int i=2;i<=temp;i++){
            if(n%i==0){
            return false;
            }
        }
        return true;
    }

然后后面可以优化的就是33和40行都调用了equals，完全可以写到一起。这些细节都可以优化。
如果还过不了，用哈希表试试？