Semi-Prime

Semi-Prime

时间： 1ms        内存：64M

描述：

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.

输入：

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

输出：

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

示例输入：

3
4
6
12

示例输出：

No
Yes
Yes
No

提示：

参考答案（内存最优[976]）：

#include<stdio.h>
#include<math.h>
int main()
{
 int prime(int);
 int n;
 while(scanf("%d",&n)!=EOF) 
 { 
  int i,t=sqrt(n),k=0,a; 
  if(prime(n))  
   printf("No\n"); 
  else  
  {  
   for(i=2;i<=t;i++)   
    if(n%i==0)    
    {    
     k++;    
     a=i;    
    }   
    if(k>1)
     printf("No\n");   
    else
     if(prime(a) && prime(n/a))
      printf("Yes\n");
     else
      printf("No\n");
  }
 }
 return 0;
}
int prime(int n)
{
 int i,t;
 t=sqrt(n);
 for(i=2;i<=t;i++)
  if(n%i==0)
   break;
  if(i>t)
   return 1;
  return 0;
}

参考答案（时间最优[0]）：

#include<stdio.h>
#include<math.h>
int main()
{
 int prime(int);
 int n;
 while(scanf("%d",&n)!=EOF) 
 { 
  int i,t=sqrt(n),k=0,a; 
  if(prime(n))  
   printf("No\n"); 
  else  
  {  
   for(i=2;i<=t;i++)   
    if(n%i==0)    
    {    
     k++;    
     a=i;    
    }   
    if(k>1)
     printf("No\n");   
    else
     if(prime(a) && prime(n/a))
      printf("Yes\n");
     else
      printf("No\n");
  }
 }
 return 0;
}
int prime(int n)
{
 int i,t;
 t=sqrt(n);
 for(i=2;i<=t;i++)
  if(n%i==0)
   break;
  if(i>t)
   return 1;
  return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。