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 P1 and P2 that given number is equal to P1*P2. 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 109. 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
6
Sample Output
Yes 思路:nearly prime数只能有两个质因数
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
int n,num;
bool nearlyprime(){
int cnt=0;
int r=sqrt((double)num);
if((num&1)==0){
while((num&1)==0){
num>>=1;
cnt++;
if(cnt>2)return false;
}
}
for(int i=3;i<=r;i+=2){
if(num%i==0){
while(num%i==0){
num/=i;
cnt++;
if(cnt>2)return false;
}
}
}
if(num!=1)cnt++;
return cnt==2;
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&num);
if(nearlyprime())puts("Yes");
else puts("No");
}
return 0;
}