试除法判定质数

试除法判定质数

题目： 给定 n 个正整数 ai，判定每个数是否是质数。

输入格式 第一行包含整数 n。

接下来 n 行，每行包含一个正整数 ai。

输出格式 共 n 行，其中第 i 行输出第 i 个正整数 ai 是否为质数，是则输出 Yes，否则输出 o。

数据范围 1≤n≤100, 1≤ai≤21−1 输入样例： 2 2 6 输出样例： Yes o

提交代码：

import java.util.*;

public class Main
{
    static int n;
    static int [] a = new int [110];
    public static void main(String[] args)
    {
        Scanner in = new Scanner (System.in);      
        n = ();
        for (int i = 0; i < n; ++ i) a[i] = ();
        for (int i = 0; i < n; ++ i)
        {
            if (isPrime(a[i])) println("Yes");
            else println("o");
        }
    }
    public static boolean isPrime(int x)
    {
        if (x < 2) return false;
        // 这里的 i <= n / i 的原理等于 i * i <= n 但是不推荐后者 
        // 因为后者可能i * i 最后结果超出int范围
        // 也不推荐 i <= sqrt(n) 因为 sqrt这个函数很慢
        for (int i = 2; i <= x / i; ++ i) if (x % i == 0) return false;
        return true;
    }
}