113. Nearly prime numbers
time limit per test: 0.25 sec.memory limit per test: 4096 KB
Nearly prime number is an integer positive number for which it is possible to find such primesP1andP2that given number is equal toP1*P2. There is given a sequence onNinteger positive numbers, you are to write a program that prints “Yes” if given number is nearly prime and “No” otherwise.
Input
Input file consists ofN+1 numbers. First is positive integerN (1N10). NextNnumbers followed byN. Each number is not greater than109. All numbers separated by whitespace(s).
Output
Write a line in output file for each number of given sequence. Write “Yes” in it if given number is nearly prime and “No” in other case.
Sample Input
16
Sample Output
Yes
Author: Michael R. Mirzayanov
Resource: PhTL #1 Training Contests
Date: Fall 2001
思路：我的想法是先对100000以内的素数打表，然后在用每个数依次除以素数表中的数，看那个得数是否是素数，，是则Yes，否则No，其实直接判断两个因数是否都为素数就可以啦（反正复习一遍素数打表啦）
AC代码：
#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;int N;int sum;//记录100000以内素数总数 int a;int b[100005];int prime[10000];//记录100000以内素数 void init() {prime[0] = 2;sum = 1;for(int i = 3; i < 100001;i += 2) {if(b[i] == 0) {prime[sum++] = i; b[i] = 1;for(int j = i*2; j < 100001; j += i) {b[j] = 1;}}}}bool is_prime(int x) {if(x < 2) return 0;if(x == 2 || x == 3) return 1;for(int i = 2; i <= sqrt(x*1.0); i++) {if(x % i == 0) return 0;}return 1;}void judge(int x) {bool flag = false;int i = 0, t;while(i < sum && (t = x / prime[i])){if(prime[i] * t == x && is_prime(t)) {flag = true;break;}else i++;}if(flag) printf("Yes\n");else printf("No\n");}int main() {init();scanf("%d", &N);while(N–) {scanf("%d", &a);judge(a);}return 0;}
还要高声歌唱。那歌声，一定是响遏流云的，
