// yukicoder: No.312 置換処理 // 2019.4.19 bal4u #include #include //// 素数テスト long long calc_pow(int a, long long k, long long n) { long long p; unsigned long long bit; p = 1; for (bit = 0x8000000000000000U; bit > 0; bit >>= 1) { if (p > 1) p = (p*p) % n; if (k & bit) p = (p*a) % n; } return p % n; } int suspect(int b, long long n) { int i, t; long long u, n1; long long x0, x1; u = n1 = n - 1; t = 0; while ((u & 1) == 0) { t++; u >>= 1; } x0 = calc_pow(b, u, n); for (i = 1; i <= t; i++) { x1 = (x0*x0) % n; if (x1 == 1 && x0 != 1 && x0 != n1) return 0; x0 = x1; } return x1 == 1; } int prime_test(long long n) { if (n == 1) return 0; /* 1 */ if (n == 2 || n == 3) return 1; /* 2, 3 */ if ((n & 1) == 0) return 0; /* other even integers */ if (!suspect(2, n)) return 0; if (n <= 1000000) { if (!suspect(3, n)) return 0; } else { if (!suspect(7, n)) return 0; if (!suspect(61, n)) return 0; } return 1; } int main() { int b, a; long long N, ans; scanf("%lld", &N); ans = N, b = (int)sqrt((double)N); if ((N & 1) == 0 && N != 4) N >>= 1, ans = N; if (!prime_test(N)) { for (a = 3; a <= b; a++) { if (N % a == 0) break; } if (a <= b) ans = a; } printf("%lld\n", ans); return 0; }