题解 | 素数判断 | 试除法的6k±1优化法

#include <iostream>
using namespace std;

// 优化方向：缓存/埃氏筛、线性筛/Miller-Rabin算法
// 当前算法是试除法的6k±1优化法
bool isPrime(int n){
    if(n<2) return false;
    else if(n==2 || n==3) return true;
    else if(!(n&1) || n%3==0) return false;
    for(int i=5;i*i<=n;i+=6)
        if(n%i==0 || n%(2+i)==0) return false;
    return true;
}

int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int tests;cin>>tests;
    while(tests--){
        int cur;cin>>cur;
        cout<<(isPrime(cur)?"Yes":"No")<<'\n';
    }

    return 0;
}