SGU 113

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 primes P₁ and P₂ that given number is equal to P₁*P₂. There is given a sequence on N integer positive numbers, you are to write a program that prints “Yes” if given number is nearly prime and “No” otherwise.

Input

Input file consists of N+1 numbers. First is positive integer N (1￡N￡10). Next N numbers followed by N. Each number is not greater than 10⁹. 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

1

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 using namespace std;
 6 
 7 int n;
 8 
 9 bool judge(int x) {
10         int sum = 0;
11         int t;
12         for(int i = 2; i * i <= x; i++) {
13                 if(x % i == 0 ) {
14                         sum++;
15                         t = i;
16 
17                 }
18         }
19 
20         return sum == 1 && ((x / t == t) || x / t % t != 0) ;
21 }
22 int main()
23 {
24 
25     scanf("%d",&n);
26 
27     for(int i = 1; i <= n; i++) {
28             int ch;
29             scanf("%d",&ch);
30             if(judge(ch)) printf("Yes\n");
31             else printf("No\n");
32     }
33     return 0;
34 }

View Code

6

Sample Output

Yes

 易知，我们要寻找的数除1 与自身外其他的因子数必然不超过2，假设有两个因子，则其中一个因子必然不能整除另一个因子。

SGU 113,布布扣,bubuko.com

SGU 113

原文：http://www.cnblogs.com/hyxsolitude/p/3585343.html