题解 | 素数判断

#include <iostream>
#include <cmath>
using namespace std;

bool isPrime(int n) {
    if (n <= 1) return false;    // 1及以下不是素数
    if (n <= 3) return true;     // 2和3是素数
    if (n % 2 == 0 || n % 3 == 0) return false; // 排除能被2或3整除的数

    // 只需检查6k±1形式的数（5,7,11,13...）
    for (int i = 5; i <= sqrt(n); i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }
    return true;
}

int main() {
    int T,num,i;
    cin>>T;
    for(i=1;i<=T;i++)
    {cin >> num;

    if (isPrime(num)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }}

    return 0;
}