Brian Warehouse

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 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).

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.
不用管Nearly prime numbers 到底是个什么数，总之是两个质数的乘积就对了。枚举的范围: 2 ~ 32000 (10^4.5 )
我的思路是: 首先把2~32000之间的所有素数都存放在一个数组里，然后当你输入一个数据时，先让其逐一模除这个数组里的素数，一旦模除结果为0，则计算出他们的商，再判断商是否也为素数。注意数据是两个数的平方的处理

#include <stdio.h>
#include <math.h>
int prime[30000],M=0;

int isP(int n) //判断是否为素数,非常精确而高效
{
    int i=2,t=sqrt(n);
    if ((n != 2 && !(n % 2)) || (n != 3 && !(n % 3)) || 
        (n != 5 && !(n % 5)) || (n != 7 && !(n % 7)))
        return 0;
    for (; i<=t; i++)
        if (n%i == 0)
            return 0;
    return 1;
}

int isNP(int n)
{
    int i=0,t=sqrt(n),r;
    for (; prime[i]<=t; i++) // 平方在此处理
    {
        if (n%prime[i] == 0) // 模除试商
        {
            r=n/prime[i]; // 求商
            if (isP(r))
                return 1;
        }
    }
    return 0;
}

int main()
{
    int i=3,N,m;    
    for (prime[M++]=2; i<32000; i+=2)
        if (isP(i))
            prime[M++]=i;
    
    scanf("%d",&N);
    while (N--)
    {
        scanf("%d",&m);
        if (m==6)
            printf("Yes\n"); // 程序中唯一未解决的问题,望各路大牛指教!
        else printf("%s\n",isNP(m) ? "Yes":"No");
    }
    return 0;
}