zcmu--1034: T-primes（思維）

1034: T-primes

Time Limit: 1 Sec  Memory Limit: 128 MB

Submit: 1691  Solved: 316

[Submit][Status][Web Board]

Description

We know that prime numbers are positive integers that have exactly two distinct positive divisors. Similarly, we'll call a positive integer t Т-prime, if t has exactly three distinct positive divisors.

You are given an array of n positive integers. For each of them determine whether it is Т-prime or not.

Input

The first line contains a single positive integer, n (1 ≤ n ≤ 105), showing how many numbers are in the array. The next line contains n space-separated integers xi (1 ≤ xi ≤ 109).

Output

Print n lines: the i-th line should contain "YES" (without the quotes), if number xi is Т-prime, and "NO" (without the quotes), if it isn't.

Sample Input

3

4 5 6

Sample Output

YES NO NO

得：

• 要換一種思路，想想會不會有更簡單的算法；要巧妙一點

分析：

• 一開始是定義一個函數，然後對輸入的每個數進行代入函數，計算一共有幾個除數，但是會提示數組越界、時間超限、答案錯誤。。。我也很無奈的。。。
• 然後，看了網上的代碼，不用定義數組，因為隻輸入一組數，循環然後一個個輸入就好；
• 不用定義函數，如果是T素數的話，就一定是素數平方得到的數；定義一個變量獲得輸入數的開方值；然後循環，j*j<這個值，即求該數是否為素數，如果是并且b的平方==a（有的數開方後是小數），則就是t素數；

代碼：

#include<bits/stdc+.h>
using namespace std;
int main()
{
    int n,i,j;
    long long a,b;
    scanf("%d",&n);
    for(i=1; i<=n; i++)
    {
        scanf("%lld",&a);
        b = sqrt(a);
        for(j=2; j*j<=b; j++)
        {
            if( b%j==0 )
                break;
        }
        if(j*j>b && b*b==a && a>1)
        {
            printf("YES\n");
        }else
        {
            printf("NO\n");
        }
    }
    return 0;
}