230-B, *1300

Problem - 230B - Codeforces

문제

• 답을 $n(1 \leq n \leq 10^{5})$번 출력한다
• $x(1 \leq x \leq 10^{12})$가 주어졌을 때, $x$의 양의 약수가 3개인가?

 

$O(\sqrt{x}+nlog\ x)$

양의 약수가 3개인 수는 $$p^{2},\ \mathrm{p\ is\ prime}$$꼴의 수이다

먼저, 에라토스테네스의 체(sieve of eratosthenes)를 이용하여 소수를 구하고 $O(\sqrt{x}log\ log\ \sqrt{x}) \approx O(\sqrt{x})$ 
이 소수를 set 에 저장한다 $O(log\ \pi(\sqrt{x})!) \approx O(\sqrt{x})$

이제 수들이 주어질 때마다
i) 완전제곱수인지? $O(log\ x)$
ii) $\sqrt{x}$가 소수인지? $O(log\ \sqrt{x})$
파악한다 $O(nlog\ x)$

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
set<int> p;
bool seive[1000001] {};
 
void find_prime()
{
    seive[2] = true;
    for(int i = 3; i < size(seive); i += 2) seive[i] = true;
    for(int i = 3; i*i < size(seive); i += 2){
        if(seive[i]){
            for(int j = i*i; j < size(seive); j += i) seive[j] = false;
        }
    }
 
    for(int i = 2; i < size(seive); i++){
        if(seive[i]) p.insert(i);
    }
}
 
bool isTprime(long long x)
{
    long long sr = sqrt(x);
    if(sr*sr == x && p.find((int) sr) != p.end()) return true;
    else return false;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int n;
    cin >> n;
    long long x;
    find_prime();
    while(n--){
        cin >> x;
        cout << (isTprime(x)? "YES": "NO") << endl;
    }
 
    if(p.find(988027) != p.end()) cout << "prime" << endl;
 
    return 0;
}cs