#include #include #include #include typedef uint8_t u8; typedef uint16_t u16; typedef uint32_t u32; typedef uint64_t u64; typedef int8_t s8; typedef int16_t s16; typedef int32_t s32; typedef int64_t s64; const int INF = (1 << 28); const long INFL = (1LL << 50); class FastIO { public: void flush() { fflush(stdin); fflush(stdout); } FastIO& operator >> (int &right) { if( scanf("%d", &right) == EOF ) { fprintf(stderr, "cannot scanf()."); exit(1); } return *this; } FastIO& operator >> (u64 &right) { if( scanf("%ld", &right) == EOF ) { fprintf(stderr, "cannot scanf()."); exit(1); } return *this; } FastIO& operator >> (u32 &right) { if( scanf("%d", &right) == EOF ) { fprintf(stderr, "cannot scanf()."); exit(1); } return *this; } FastIO& operator >> (double &right) { if( scanf("%lf", &right) == EOF ) { fprintf(stderr, "cannot scanf()."); exit(1); } return *this; } FastIO& operator >> (char &right) { if( scanf("%c", &right) == EOF ) { fprintf(stderr, "cannot scanf()."); exit(1); } return *this; } FastIO& operator >> (char right[]) { if( scanf("%s", right) == EOF ) { fprintf(stderr, "cannot scanf()."); exit(1); } return *this; } FastIO& operator << (const int& right) { printf("%d", right); return *this; } FastIO& operator << (int&& right) { printf("%d", right); return *this; } FastIO& operator << (const u32& right) { printf("%d", right); return *this; } FastIO& operator << (u32&& right) { printf("%d", right); return *this; } FastIO& operator << (const u64& right) { printf("%ld", right); return *this; } FastIO& operator << (u64&& right) { printf("%ld", right); return *this; } FastIO& operator << (const long& right) { printf("%ld", right); return *this; } FastIO& operator << (long&& right) { printf("%ld", right); return *this; } FastIO& operator << (const double& right) { printf("%.20lf", right); return *this; } FastIO& operator << (double&& right) { printf("%.20lf", right); return *this; } FastIO& operator << (const char right[]) { printf("%s", right); return *this; } FastIO& operator << (const char& right) { printf("%c", right); return *this; } FastIO& operator << (char&& right) { printf("%c", right); return *this; } }; FastIO io; template class Pair { public: T first; U second; Pair() {} Pair(T first_, U second_) : first(first_), second(second_) {} }; class MillerRabin { public: u64 modmul_64(u64 a, u64 b, u64 mod) { u64 res = 0; a %= mod; for(s32 i = 63; i >= 0; --i) { res = (res << 1) % mod; if( ((b >> i) & 0x01) == 1 ) { res = (res + a) % mod; } } return res; } u64 modpow_64(u64 a, u64 b, u64 mod) { u64 res = 1, p = a; a %= mod; b %= mod; while( b != 0 ) { if( (b & 0x01) != 0 ) { res = modmul_64(res, p, mod); } p = modmul_64(p, p, mod); b >>= 1; } return res; } bool operator () (u64 N) { u32 k = 16; if( N == 2 ) return true; if( N <= 1 or N % 2 == 0 ) return false; u64 d = (N - 1); u64 s = 0; while( d % 2 == 0 ) { d >>= 1; s += 1; } for(s32 i = 0; i < k; ++i) { u64 a = (((u64)rand() << 32) | (u64)rand()) % (N - 2) + 1; u64 r = modpow_64(a, d, N); if( r == 1 ) continue; if( r == N - 1 ) continue; for(s32 j = 1; j < s; ++j) { r = modpow_64(r, 2, N); if( r == N - 1 ) { goto label_1; } } return false; label_1:; } return true; } }; template void Swap(T& arg1, T& arg2) { T temp = arg1; arg1 = arg2; arg2 = temp; } u32 gcd(u32 a, u32 b) { if( a < b ) Swap(a, b); while( b != 0 ) { a = a % b; Swap(a, b); } return a; } u64 gcd(u64 a, u64 b) { if( a < b ) Swap(a, b); while( b != 0 ) { a = a % b; Swap(a, b); } return a; } class PollardsRho { public: u64 modmul_64(u64 a, u64 b, u64 mod) { u64 res = 0; a %= mod; for(s32 i = 63; i >= 0; --i) { res = (res << 1) % mod; if( ((b >> i) & 0x01) == 1 ) { res = (res + a) % mod; } } return res; } u64 operator () (u64 N) { u64 x = 2; u64 y = 2; u64 d = 1; while( d == 1 ) { x = modmul_64(x, x, N); u64 ty = modmul_64(y, y, N); y = modmul_64(ty, ty, N); d = gcd(llabs(x - y), N); } if( d == N ) { return 0; } return d; } }; class PrimeFactorization { public: u64 primes_[1024]; u64 p_num_[1024]; u64 num_; public: void operator () (u64 N) { num_ = 0; for(s32 i = 2; i < 1000000; ++i) { if( N % i == 0 and N != 0 ) { primes_[num_] = i; p_num_[num_] = 1; num_ += 1; N /= i; while( N % i == 0 and N != 0 ) { p_num_[num_ - 1] += 1; N /= i; } } } if( N == 1 ) return; split(N); } void split(u64 N) { if( N == 1 ) return; MillerRabin mr; for(s32 i = 0; i < num_; ++i) { if( N % primes_[i] == 0 ) { p_num_[i] += 1; split(N / primes_[i]); return; } } u64 root = (u64)sqrt(N); if( root * root == N ) { split(root); split(root); return; } if( mr(N) ) { primes_[num_] = N; p_num_[num_] = 1; num_ += 1; return; } u64 a, b; split2(N, a, b); split(a); split(b); } void split2(u64 N, u64& a, u64& b) { PollardsRho pr; a = pr(N); b = N / a; } }; static bool isprime[10000000]; int main() { PrimeFactorization pf; u64 N; io >> N; io.flush(); pf(N); int t = 0; for(s32 i = 0; i < pf.num_; ++i) { t += pf.p_num_[i]; //io << pf.primes_[i] << ' ' << pf.p_num_[i] << '\n'; } io << ( t >= 3 ? "YES" : "NO" ) << '\n'; io.flush(); return 0; }