Morris' Blog

2012-10-12 13:00:47Morris

[ZJ][sieve] a505. B. T-primes

留言 1 收藏 0 推薦 0

內容：

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.

輸入說明：

The first line contains a single positive integer, n (1 ≤ n ≤ 10⁶), showing how many numbers are in the array. The next line contains nspace-separated integers x_i (1 ≤ x_i ≤ 10¹⁴).

輸出說明：

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

範例輸入：

3
4 5 6

範例輸出：

YES
NO
NO

提示：

n,xi範圍與原題不同！

測試資料較大！請使用較快的輸出入！

2012/10/11 加強測資！

出處：

CodeForce 230B T-primes (管理：eddy841021)

/**********************************************************************************/
/* Problem: a505 "B. T-primes" from CodeForce 230B T-primes                      */
/* Language: C (687 Bytes)                                                       */
/* Result: AC(350ms, 1.5MB) judge by this@ZeroJudge                              */
/* Author: morris1028 at 2012-10-11 23:31:01                                     */
/**********************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define LL long long
#define maxL (10000000>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
int mark[maxL];
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 10000000;
    for(i = 2; i <= n; i++) {
        if(!GET(i)) {
            for(k = n/i, j = i*k; k >= i; k--, j -= i)
                SET(j);
        }
    }
}
main() {
    sieve();
    int t;
    LL n, m;
    scanf("%d", &t);
    while(t--) {
        scanf("%lld", &n), m = sqrt(n);
        if(m*m != n || GET(m))
            puts("NO");
        else    puts("YES");
    }
    return 0;
}

上一篇：[ZJ] a473. 外援計畫

下一篇：[ZJ][插頭DP] a228. 就少一個插座用很不方便