//Pollard-Rho模版 #include <bits/stdc++.h> #define N 1000005 #define int long long using namespace std; int n, seed; set<int> pri; inline int rnd(int x) { int a = rand() % 1145 + 1; x *= a; x ^= x << 13; x ^= x >> 7; x ^= x << 17; x /= a; return abs(x); } int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } inline int ksmi(int a, int b, int p) { int res = 1; while (b) { if (b & 1) res = res * a % p; b >>= 1; a = a * a % p; } return res; } bool Miller_Rabin(long long p) { if (p < 2) return 0; if (p == 2 || p == 3) return 1; int d = p - 1, r = 0; while (!(d & 1)) { r++; d >>= 1; } for (int k = 0; k < 10; k++) { int c = seed = rnd(seed); int a = c % (p - 2) + 2; int x = ksmi(a, d, p); if (x == 1 || x == p - 1) continue; for (int i = 0; i < r - 1; i++) { x = (__int128)x * x % p; if (x == p - 1) break; } if (x != p - 1) return 0; } return 1; } inline int f(int x, int c, int p) { return (x * x % p + c) % p; } int Pollard_Rho(int n) { if (!(n & 1)) return 2; int a = seed = rnd(seed); int c = a % (n - 1) + 1; int t = f(0, c, n), r = f(f(0, c, n), c, n); while (t != r) { int d = gcd(abs(t - r), n); if (d > 1) return d; t = f(t, c, n); r = f(f(r, c, n), c, n); } return n; } void fac(long long x) { if (x < 2) return; if (Miller_Rabin(x)) { pri.insert(x); return; } long long p = x; while (p >= x) p = Pollard_Rho(x); while ((x % p) == 0) x /= p; fac(x), fac(p); return ; } signed main() { srand((unsigned)time(0)); seed = rand(); scanf("%lld", &n); fac(n); for (int p : pri) { printf("%lld ", p); } return 0; }