#line 1 "main.cpp" #include #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--) #define all(x) (x).begin(), (x).end() #define sz(x) int(x.size()) using namespace std; using ll = long long; constexpr int INF = 1e9; constexpr ll LINF = 1e18; string YesNo(bool cond) { return cond ? "Yes" : "No"; } string YESNO(bool cond) { return cond ? "YES" : "NO"; } template bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; } template bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } return false; } template T bisect(T ok, T ng, const F& f) { while (abs(ok - ng) > 1) { T mid = min(ok, ng) + (abs(ok - ng) >> 1); (f(mid) ? ok : ng) = mid; } return ok; } template T bisect_double(T ok, T ng, const F& f, int iter = 100) { while (iter--) { T mid = (ok + ng) / 2; (f(mid) ? ok : ng) = mid; } return ok; } template vector make_vec(size_t a) { return vector(a); } template auto make_vec(size_t a, Ts... ts) { return vector(ts...))>(a, make_vec(ts...)); } template istream& operator>>(istream& is, vector& v) { for (int i = 0; i < int(v.size()); i++) { is >> v[i]; } return is; } template ostream& operator<<(ostream& os, const vector& v) { for (int i = 0; i < int(v.size()); i++) { os << v[i]; if (i < sz(v) - 1) os << ' '; } return os; } #line 4 "/Users/gyouzasushi/kyopro/library/math/factorize.hpp" long long modmul(long long x, long long y, long long mod) { using i128 = __int128_t; return (long long)(i128(x) * i128(y) % i128(mod)); } long long modpow(long long a, long long n, long long mod) { long long ret = 1; while (n > 0) { if (n & 1) ret = modmul(ret, a, mod); a = modmul(a, a, mod); n >>= 1; } return ret; } long long rho(long long n) { long long z = 0; auto f = [&](long long x) -> long long { long long ret = modmul(x, x, n) + z; if (ret == n) return 0; return ret; }; while (true) { long long x = ++z; long long y = f(x); while (true) { long long d = std::gcd(std::abs(x - y), n); if (d == n) break; if (d > 1) return d; x = f(x); y = f(f(y)); } } } #include bool miller_rabin(long long n) { if (n == 1) return 0; long long d = n - 1, s = 0; while (~d & 1) d >>= 1, s++; auto check = [&](long long a) -> bool { long long x = modpow(a, d, n); if (x == 1) return 1; long long y = n - 1; for (int i = 0; i < s; i++) { if (x == y) return true; x = modmul(x, x, n); } return false; }; for (long long a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) { if (a >= n) break; if (!check(a)) return false; } return true; } #line 59 "/Users/gyouzasushi/kyopro/library/math/factorize.hpp" std::map factorize(long long n) { std::map ret; while (~n & 1) n >>= 1, ret[2]++; std::queue q; q.push(n); while (!q.empty()) { long long p = q.front(); q.pop(); if (p == 1) continue; if (miller_rabin(p)) { ret[p]++; continue; } long long d = rho(p); q.push(d); q.push(p / d); } return ret; } #line 72 "main.cpp" int main() { ll n; cin >> n; cout << YesNo(sz(factorize(n)) <= 2) << '\n'; }