题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1723
水题。
果断卖萌,
敲上 素数筛选和素数判断。。
弱爆了!!
#include <stdio.h> #include <math.h> #include <string.h> #define M 1005 bool mark[M]; void sieve_prime() { memset(mark, true, sizeof(mark)); mark[0] = mark[1] = false; for (int i=2; i<=sqrt(M); i++){ if(mark[i]){ for(int j=i*i; j<M; j+=i) mark[j]= false; } } } inline bool is_prime(int u){ int i; for(i=2;i*i<=u;i++) if(u%i==0) return false; return true; } int main() { int n; int i, j; bool flag; int k; sieve_prime(); while(scanf("%d", &n) != EOF){ i=2; k = sqrt(n); flag = false; while(1){ if(i>k) break; j = n/i; if(mark[i] && j*i == n) if(is_prime(j)){ flag= true; break; } i++; } if(flag) printf("Yes\n"); else printf("No\n"); } return 0; }