题目描述

质数-试除法判定

JAVA 代码

/**
 * 求质数公式 n%i == 0
 * 剪枝: 只用算到 sqrt(n) --> 
 * 因为 因子成对出现. 
 * 例子 n = 6; 只算到 sqrt(6);
 * 算到能被 小于sqrt(n)就足够了. 
 */

import java.util.*;
import java.io.*;

class Main{
    static boolean prime(int a){
        if(a<2) return false;
        //剪枝
        for(int i=2; i<a/i; i++){
            //公式
            if(a%i==0) return false;
        }
        return true;
    }

    public static void main(String args[]){

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        for(int i=0;i<n;i++){

            if(prime(sc.nextInt())) System.out.println("Yes");
            else System.out.println("No");
        }
    }
}