$$\color{Red}{试除法判定质数:两种语言}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

题目介绍

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

输入格式

第一行包含整数 n。

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

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

数据范围

1 ≤ n ≤ 100

1 ≤ ai ≤ 2^31 − 1

输入样例：

2
2
6

输出样例：

Yes
No

证明

一个数为质数的定义是，约数只有1和它本身，即：它不能整除2 -> n-1中的任何数字。

暴力做法：

枚举一个数 2 -> n-1，看能否整除，都不能则为质数，则这道题做法为O（n^2）,显然会超时。

进阶做法：一个数n存在约数的话，必然存在一个对偶的约数，相乘为这个数字本身。
也必然满足这两个对偶的约数，一个大于等于根号n,一个小于等于根号n。

那么我们可以枚举的时候从2枚举到根号n，这样就是O(nlog(n))

这里我们数据范围最大到2 ^ 31 - 1，已经到了int的极限，如果for循环条件是i * i <= n会爆int，不可取。

而我们使用sqrt（）函数，每个数字都要计算一次，速度也不是最快的，最快的方法：试除法：

    static boolean is_prime(int x){
        if (x < 2) return false;
        for (int i = 2; i <= x / i; i++) {
            if (x % i == 0) return false;
        }
        return true;
    }

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int n;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static boolean is_prime(int x){
        if (x < 2) return false;
        for (int i = 2; i <= x / i; i++) {
            if (x % i == 0) return false;
        }
        return true;
    }

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            int x = Integer.parseInt(br.readLine());
            if (is_prime(x)) System.out.println("Yes");
            else System.out.println("No");
        }
    }
}

C++

#include <iostream>

using namespace std;

bool is_prime(int x)
{
    if(x < 2)   return false;
    for(int i=2; i <= x / i; i++)
        if(x % i == 0)  return false;
    return true;
}

int main()
{
    int n, x;
    cin >> n;
    while(n--)
    {
        scanf("%d", &x);
        if(is_prime(x)) puts("Yes");
        else    puts("No");
    }
    return 0;
}