#include <bits/stdc++.h> using namespace std; #define N 100000 int main(){ int T, num; int i, j, max=0; //定义一个全为true的数组 埃拉托色尼筛选法 //建立一个质数哈希表 isPrime[4] = false不是质数 isPrime[2]=true是质数 bool isPrime[N] = {false,false}; // 2-N默认全是质数 for(i=2; i<N; i++) isPrime[i] = true; for(i=2; i<N; i++){ if(isPrime[i]){ for(j=i+i; j<N; j=j+i){ //将质数的倍数全部置为false 比如2的倍数 4 6 8 10 12…… isPrime[j] = false; } } } cin>>T; while(T--){ cin>>num; if(isPrime[num]) cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }
全部评论
(0) 回帖