題干：

給出N個(gè)正整數(shù)，檢測(cè)每個(gè)數(shù)是否為質(zhì)數(shù)。如果是，輸出"Yes"，否則輸出"No"。

Input

第1行：一個(gè)數(shù)N，表示正整數(shù)的數(shù)量。(1 <= N <= 1000)?
第2 - N + 1行：每行1個(gè)數(shù)(2 <= Sii?<= 10^9)

Output

輸出共N行，每行為 Yes 或 No。

Sample Input

5 2 3 4 5 6

Sample Output

Yes Yes No Yes No

?

解題報(bào)告：

? ? 不能預(yù)處理，會(huì)超時(shí)的。每次sqrt(n)就足夠了。sqrt(1e9)=30000左右，這樣總最差復(fù)雜度就是o(1000*30000)也就是個(gè)1e7。不會(huì)炸，但是如果n*log(logn)的預(yù)處理就不太辦了。。

AC代碼：

#include<bits/stdc++.h>using namespace std; bool isprime(int x) {for(int i = 2; i*i<=x; i++){if(x%i==0) return 0;}return 1; }int main() {int n;int qq;cin>>n;while(n--) {scanf("%d",&qq);if(isprime(qq) ) printf("Yes\n");else printf("No\n");}return 0 ; }

?

總結(jié)

以上是生活随笔為你收集整理的【51Nod - 1106 】质数检测 （水题，数论）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。