CodeForces 230B T-primes

淩亂°似流年 2022-02-21 14:51 118阅读 0赞

题目衔接：[http://codeforces.com/problemset/problem/230/B][http_codeforces.com_problemset_problem_230_B]

> B. T-primes
> 
> time limit per test
> 
> 2 seconds
> 
> memory limit per test
> 
> 256 megabytes
> 
> input
> 
> standard input
> 
> output
> 
> standard output
> 
> 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 *x**i* (1 ≤ *x**i* ≤ 1012).
> 
> Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is advised to use the cin, cout streams or the %I64dspecifier.
> 
> Output
> 
> 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.

>  
> 
> Examples
> 
> input
> 
> Copy
> 
>     3
>     4 5 6
> 
> output
> 
> Copy
> 
>     YES
>     NO
>     NO
> 
> Note
> 
> The given test has three numbers. The first number 4 has exactly three divisors — 1, 2 and 4, thus the answer for this number is "YES". The second number 5 has two divisors (1 and 5), and the third number 6 has four divisors (1, 2, 3, 6), hence the answer for them is "NO".

题目大意：现在重新定义一个T素数，这个数只能被1自己和另外一个因子整除，即只有三个因子，现在让你判断是不是T素数

思路：既然只有三个因子，那么第三个一定是它的平方根，而且它的平方根还不能有其他因子，即平方根为素数！，知道了后就直接打表，判断是不是素数即可。

代码：

/*
    
    */
    #include<map>
    #include<set>
    #include <vector>
    #include<stack>
    #include<queue>
    #include<cmath>
    #include<string>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define ll unsigned long long
    #define inf 0x3f3f3f
    #define esp 1e-8
    #define bug {printf("mmp\n");}
    #define mm(a,b) memset(a,b,sizeof(a))
    #define T() int test,q=1;scanf("%d",&test); while(test--)
    const int maxn=1e6+10;
    const double pi=acos(-1.0);
    const int N=201;
    const int mod=1e9+7;
    bool a[maxn];
    void ff()
    {
        a[1]=true;
        for(int i=2;i<=maxn;i++)
        {
            if(a[i]==false)
            {
                for(int j=i*2;j<=maxn;j+=i)
                    a[j]=true;
            }
        }
    }
    
    int main()
    {
        ff();
        T()
        {
            ll n;
            cin>>N;
            double ans=sqrt(n);
            int m=ans;
            if(m==ans)
            {
                if(!a[m])
                    cout<<"YES\n";
                else
                    cout<<"NO"<<endl;
            }
            else
                cout<<"NO"<<endl;
        }
    
        return 0;
    }

[http_codeforces.com_problemset_problem_230_B]: http://codeforces.com/problemset/problem/230/B