Yukicoder036 素数が嫌い！

問題概要

$N$が、”素数、1、使う数自身” 以外で割り切れるかどうか判定せよ。

$N\leqq10^{14}$

yukicoder036

解法

合成数と素数の積であるかどうかという質問と見ることができる。
したがって素因数が3以上でOK

計算量:$O(\sqrt N)$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    
    LL N;
    LL ans = 0LL;
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        cin >> N;
        int cnt = 0;
        for (LL i = 2; i*i <= N; i++) {
            while (N%i == 0) {
                N /= i;
                cnt++;
            }
        }
        if (N != 1)cnt++;
        cout << (cnt > 2 ? "YES" : "NO") << "\n";
    
        return 0;
    }