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 到底是個(gè)什么數(shù)，總之是兩個(gè)質(zhì)數(shù)的乘積就對(duì)了。枚舉的范圍: 2 ~ 32000 (10^4.5 )
我的思路是: 首先把2~32000之間的所有素?cái)?shù)都存放在一個(gè)數(shù)組里，然后當(dāng)你輸入一個(gè)數(shù)據(jù)時(shí)，先讓其逐一模除這個(gè)數(shù)組里的素?cái)?shù)，一旦模除結(jié)果為0，則計(jì)算出他們的商，再判斷商是否也為素?cái)?shù)。注意數(shù)據(jù)是兩個(gè)數(shù)的平方的處理

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

int isP(int n) //判斷是否為素?cái)?shù),非常精確而高效
{
    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"); // 程序中唯一未解決的問(wèn)題,望各路大牛指教!
        else printf("%s\n",isNP(m) ? "Yes":"No");
    }
    return 0;
}