Semi-Prime

http://acm.zju.edu.cn/show_problem.php?pid=2723

Time limit: 1 Seconds

Memory limit: 32768K

Prime Number Definition: An integer greater than one is called a prime number if its only positive divisors (factors) are one and itself. For instance, 2, 11, 67, 89 are prime numbers but 8, 20, 27 are not.

Semi-Prime Number Definition: An integer greater than one is called a semi-prime number if it can be decompounded to TWO prime numbers. For example, 6 is a semi-prime number but 12 is not.

Your task is just to determinate whether a given number is a semi-prime number.

1. Input

There are several test cases in the input. Each case contains a single integer N (2 <= N <= 1,000,000)

2. Output

One line with a single integer for each case. If the number is a semi-prime number, then output "Yes", otherwise "No".

3. Sample Input

3
4
6
12

4. Sample Output

No
Yes
Yes
No

Author: LIU, Yaoting

Problem Source: Zhejiang University Local Contest 2006, Preliminary

5. 参考程序

   1 #include <iostream>
   2 #include <cmath>
   3 using namespace std;
   4 bool semiprime(int n)
   5 {
   6      int N=sqrt(float(n));
   7      int k=0;
   8      for(int i=2;i<=N;i++)
   9      {
  10              if(n%i==0) k++;            
  11      }
  12      if(k==1) return true;  
  13      else return false;
  14      
  15  }
  16 int main()
  17 {
  18     int n;
  19     
  20     while(cin>>n)
  21     {
  22         if(semiprime(n))
  23             cout<<"Yes\n";
  24         else 
  25             cout<<"No\n";       
  26     }    
  27 }