Codeforces Round #142 (Div. 2) B. T-primes （数学、O(n)筛素数）_t-primes codeforces

http://www.codeforces.com/problemset/problem/230/B

题意：定义一个T-primes，如果一个数所有的因数只有3个，那么就称其为T-primes。让你判断N（1e5）个数，数的范围为（1e12）是不是T-primes。
解法：显然一个数如果是T-primes，那么它一定是个完全平方数，且它的平方根为一个素数，因此我们就只需要求出1e6内所有的素数即可。
用到了O（n）筛素数的方法

#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);cin.tie(0);

#define INF 0x3f3f3f3f
#define eps 1e-6
typedef long long LL;
const double pi = acos(-1.0);
const long long mod = 1e9 + 2015;
using namespace std;

const int MaxNum = 1000005;

bool isPrime[MaxNum] ; //数组定义该数字是否为素数
int prime[ MaxNum ] ; // 存下素数
int total = 0 ; //第几个素数

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    //freopen("int.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    memset(isPrime,true,sizeof(isPrime));
    memset(prime,0,sizeof(prime));
    isPrime[0] = false;
    isPrime[1] = false;
    for(int i = 2;i <= 1000005;i++)
    {
        if( isPrime[i] )
            prime[ ++ total ] = i ;
        for(int j = 1;j <= total && i * prime[j] <= 1000005;j++)
        {
            isPrime[i * prime[j]] = false ;
            if ( !(i % prime[j]) )
                break;
        }
    }
    int N;
    cin >> N;
    while(N--)
    {
        LL a;
        cin >> a;
        LL k = sqrt(a);
        if(k * k == a && isPrime[k])
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51