#include #include #include #include #include #include #include #include #include #include #include #define _fetch(_1, _2, _3, _4, name, ...) name #define rep2(i, n) rep3(i, 0, n) #define rep3(i, a, b) rep4(i, a, b, 1) #define rep4(i, a, b, c) for (int i = int(a); i < int(b); i += int(c)) #define rep(...) _fetch(__VA_ARGS__, rep4, rep3, rep2, _)(__VA_ARGS__) #define getchar getchar_unlocked #define putchar putchar_unlocked using namespace std; using i64 = long long; using u8 = unsigned char; using u32 = unsigned; using u64 = unsigned long long; using f64 = double; using f80 = long double; using u128 = __uint128_t; struct Mod64 { Mod64() : n_(0) {} Mod64(u64 n) : n_(init(n)) {} static void init_mod(u64 m) { mod = m, inv = -mul_inv(m), r2 = u128(-m) * (-m) % m; } static u64 mul_inv(u64 n) { u64 x = n; rep(_, 5) x *= 2 - n * x; return x; } static u64 reduce(u128 w) { u64 x = u64(w) * inv; u64 y = (u128(x) * mod + w) >> 64; return (y >= mod) ? y - mod : y; } static u64 init(u64 n) { return reduce(u128(n) * r2); } static u64 ilog2(u64 n) { return (n == 0) ? 0 : (63 - __builtin_clzll(n)); } Mod64& operator += (Mod64 rhs) { if ((n_ += rhs.n_) >= mod) n_ -= mod; return *this; } Mod64& operator -= (Mod64 rhs) { if (i64(n_ -= rhs.n_) < 0) n_ += mod; return *this; } Mod64& operator *= (Mod64 rhs) { n_ = reduce(u128(n_) * rhs.n_); return *this; } bool operator == (Mod64 rhs) { return n_ == rhs.n_; } bool operator != (Mod64 rhs) { return !(*this == rhs); } Mod64 operator + (Mod64 rhs) { return Mod64(*this) += rhs; } Mod64 operator - (Mod64 rhs) { return Mod64(*this) -= rhs; } Mod64 operator * (Mod64 rhs) { return Mod64(*this) *= rhs; } Mod64 operator - () { return (n_ == 0) ? *this : Mod64() - *this; }; Mod64 pow(u64 e) { if (e == 0) return Mod64(1); Mod64 ret = Mod64(*this); for (u64 mask = (u64(1) << ilog2(e)) >> 1; mask > 0; mask >>= 1) { ret *= ret; if (e & mask) ret *= *this; } return ret; } u64 val() { return reduce(n_); } friend ostream& operator << (ostream& os, Mod64& m) { return os << m.val(); } u64 n_; static u64 mod, inv, r2; }; u64 Mod64::mod = 0; u64 Mod64::inv = 0; u64 Mod64::r2 = 0; namespace factor { using m64 = Mod64; struct ExactDiv { ExactDiv() {} ExactDiv(u64 n) : n(n), i(m64::mul_inv(n)), t(u64(-1) / n) {} friend u64 operator / (u64 n, ExactDiv d) { return n * d.i; }; bool divide(u64 n) { return n / *this <= this->t; } u64 n, i, t; }; vector primes; void init(u32 n) { u32 sqrt_n = sqrt(n); vector isprime(n + 1, 1); rep(i, 2, sqrt_n + 1) if (isprime[i]) rep(j, i * i, n + 1, i) isprime[j] = 0; primes.clear(); rep(i, 2, n + 1) if (isprime[i]) primes.push_back(ExactDiv(i)); } u64 gcd(u64 a, u64 b) { while (b) { u64 t = a % b; a = b; b = t; } return a; } u64 brent(u64 n, m64 c) { // n must be composite and odd. m64::init_mod(n); const u64 s = 256; const m64 one = m64(1); auto f = [&](m64 x) { return x * x + c; }; m64 y = one; for (u64 l = 1; ; l <<= 1) { auto x = y; rep(_, l) y = f(y); m64 p = one; rep(k, 0, l, s) { rep(_, min(s, l - k)) y = f(y), p *= y - x; u64 g = gcd(n, p.n_); if (g == 1) continue; if (g == n) for (g = 1; g == 1; ) y = f(y), g = gcd(n, (y - x).n_); return g; } } } bool miller_rabin(u64 n) { if (!(n & 1)) return n == 2; if (n <= 8) return true; m64::init_mod(n); u64 d = n - 1; u64 s = __builtin_ctzll(d); d >>= s; m64 one = m64(1); auto composite = [&](m64 b) { b = b.pow(d); if (b == one || b == -one) return false; rep(_, s - 1) { b *= b; if (b == -one) return false; } return true; }; u64 bases[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}; rep(i, 7) { m64 b = m64(bases[i] % n); if (b == 0) return true; if (composite(b)) return false; } return true; } u64 ctz(u64 n) { return __builtin_ctzll(n); } u64 square(u64 n) { return n * n; } using P = pair; vector

factors(u64 n) { assert(n < (u64(1) << 63)); auto ret = vector

(); if (!(n & 1)) { u32 e = ctz(n); ret.emplace_back(2, e); n >>= e; } u64 lim = square(primes[primes.size()-1].n); rep(pi, 1, primes.size()) { auto p = primes[pi]; if (square(p.n) > n) break; if (p.divide(n)) { u32 e = 1; n = n / p; while (p.divide(n)) n = n / p, e++; ret.emplace_back(p.n, e); } } u32 s = ret.size(); while (n > lim && !miller_rabin(n)) { for (u64 c = 1; ; ++c) { u64 p = brent(n, c); if (!miller_rabin(p)) continue; u32 e = 1; n /= p; while (n % p == 0) { n /= p; e += 1; } ret.emplace_back(p, e); break; } } if (n > 1) ret.emplace_back(n, 1); if (ret.size() - s >= 2) sort(ret.begin() + s, ret.end()); return ret; } } void solve() { using namespace factor; init(1000); u64 n; while (~scanf("%llu", &n)) { u64 e = 0; for (auto p : factors(n)) { e += p.second; } puts(e >= 3 ? "YES" : "NO"); } } int main() { // clock_t beg = clock(); solve(); // clock_t end = clock(); // fprintf(stderr, "%.3f sec.\n", double(end - beg) / CLOCKS_PER_SEC); return 0; }