2012-10-12 13:00:47Morris
[ZJ][sieve] a505. B. T-primes
內容 ：
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 ≤ 106), showing how many numbers are in the array. The next line contains nspace-separated integers xi (1 ≤ xi ≤ 1014).
輸出說明
：
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.
範例輸入 ：
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;
}
好複雜@@
可以稍微指點一下嗎?