866. 试除法判定质数
给定 n 个正整数 ai，判定每个数是否是质数。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个正整数 ai。
输出格式
共 n 行，其中第 i 行输出第 i 个正整数 ai 是否为质数，是则输出 Yes，否则输出 No。
数据范围
1≤n≤100,
1≤ai≤231
输入样例：

  1. 2
  2. 2
  3. 6

输出样例：

  1. Yes
  2. No

方法一

从2到n-1遍历每个数，判断能否被n整除
时间复杂度：O(n)

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner sc = new Scanner(System.in);
  7.         int n = sc.nextInt();
  9.         while (n-- > 0) {
  10.             int x = sc.nextInt();
  11.             boolean res = isPrimer(x);
  12.             if (res) System.out.println("Yes");
  13.             else System.out.println("No");
  14.         }
  15.     }
  17.     static boolean isPrimer(int x) {
  18.         if (x <= 1) return false;
  19.         for (int i = 2; i < x; i++) {
  20.             if (x % i == 0) return false;
  21.         }
  22.         return true;
  23.     }
  24. }

方法二

从2到sqrt(n)遍历每个数，判断能否被n整除
时间复杂度：O(sqrt(n))

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner sc = new Scanner(System.in);
  7.         int n = sc.nextInt();
  9.         while (n-- > 0) {
  10.             int x = sc.nextInt();
  11.             boolean res = isPrimer(x);
  12.             if (res) System.out.println("Yes");
  13.             else System.out.println("No");
  14.         }
  15.     }
  17.     static boolean isPrimer(int x) {
  18.         if (x <= 1) return false;
  19.         for (int i = 2; i <= x / i; i++) {
  20.             if (x % i == 0) return false;
  21.         }
  22.         return true;
  23.     }
  24. }

注意for循环条件判断写成 i <= x / i 而不是 i * i <= x ，后者可能会发生溢出！ 1要进行特判！

方法三：Miller-rabin