fork download
  1. //#pragma GCC optimize("O3", "unroll-loops")
  2. //#pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt")
  3.  
  4. #include <bits/stdc++.h>
  5. #define ldb long double
  6. //#define double ldb
  7. #define db double
  8. #define unomap unordered_map
  9. #define unoset unordered_set
  10. #define endl '\n'
  11. #define str string
  12. #define strstr stringstream
  13. #define sz(a) (int)a.size()
  14. #define ll long long
  15. //#define int ll
  16. #define pii pair <int, int>
  17. #define pll pair <ll, ll>
  18. #define Unique(a) a.resize(unique(all(a)) - a.begin())
  19. #define ull unsigned ll
  20. #define fir first
  21. #define sec second
  22. #define idc cin.ignore()
  23. #define lb lower_bound
  24. #define ub upper_bound
  25. #define all(s) s.begin(), s.end()
  26. #define rev reverse
  27. #define gcd __gcd
  28. #define pushb push_back
  29. #define popb pop_back
  30. #define pushf push_front
  31. #define popf pop_front
  32. #define mul2x(a, x) a << x
  33. #define div2x(a, x) a >> x
  34. #define lcm(a, b) (a / __gcd(a, b) * b)
  35. #define log_base(x, base) log(x) / log(base)
  36. #define debug cerr << "No errors!"; exit(0);
  37. #define forw(i, a, b) for (int i = a; i <= b; ++i)
  38. #define forw2(i, a, b) for (ll i = a; i <= b; ++i)
  39. #define fors(i, a, b) for (int i = a; i >= b; --i)
  40. #define fors2(i, a, b) for (ll i = a; i >= b; --i)
  41. #define pqueue priority_queue
  42. #define sqrt sqrtl
  43. #define i128 __int128
  44. #define popcount __builtin_popcountll
  45. #define BIT(x, i) (((x) >> (i)) & 1)
  46. #define MASK(x) ((1LL) << (x))
  47. #define want_digit(x) cout << fixed << setprecision(x);
  48. #define excuting_time 1000.0 * clock() / CLOCKS_PER_SEC
  49. #define mapa make_pair
  50. using namespace std;
  51. const int MOD = 1e9 + 7; // 998244353
  52. const int inf = 1e9;
  53. const ll INF = 1e18;
  54. const int N = 1e6;
  55.  
  56. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  57. ll random(const ll &L, const ll &R) {
  58. return uniform_int_distribution<ll> (L, R) (rng);
  59. }
  60.  
  61. bitset <N + 5> p;
  62. vector <int> prime;
  63. void build() {
  64. p[0] = p[1] = 1;
  65. for (int i = 4; i <= N; i += 2) p[i] = 1;
  66. for (int i = 3; i * i <= N; i += 2) if (!p[i]) {
  67. for (int j = i * i; j <= N; j += i * 2) p[j] = 1;
  68. }
  69.  
  70. forw (i, 2, N) if (!p[i])
  71. prime.pushb(i);
  72. }
  73.  
  74. bool is_prime(int x) {
  75. if (x < 2) return false;
  76. if (x <= N) return !p[x];
  77. forw (i, 0, sz(prime) - 1) {
  78. if (prime[i] * prime[i] > x) return true;
  79. if (!(x % prime[i])) return false;
  80. }
  81. return true;
  82. }
  83.  
  84. bool maximize(int &x, const int &y) {
  85. return x < y ? x = y, true : false;
  86. }
  87.  
  88. int root(int x) {
  89. int ret = 1;
  90. forw (i, 0, sz(prime) - 1) {
  91. if (!(x % prime[i])) {
  92. ret *= prime[i];
  93. for (; !(x % prime[i]); x /= prime[i]) {}
  94. }
  95. }
  96. if (x > 1) ret *= x;
  97. return ret;
  98. }
  99.  
  100. int n;
  101. void solve() {
  102. cin >> n;
  103. build();
  104. if (is_prime(n) || n == 1) {
  105. cout << n << endl;
  106. return;
  107. }
  108. int lim = n - 1;
  109. while (!is_prime(lim)) --lim;
  110.  
  111. int mx = lim, num = lim;
  112. forw (i, lim + 1, n) {
  113. if (maximize(mx, root(i))) num = i;
  114. }
  115. cout << num << endl;
  116. }
  117.  
  118. signed main() {
  119. ios::sync_with_stdio(false), cin.tie(nullptr);
  120. srand(time(NULL));
  121. #define name "test"
  122. /*
  123.   if (fopen(name".INP", "r")) {
  124.   freopen(name".INP", "r", stdin);
  125.   freopen(name".OUT", "w", stdout);
  126.   }
  127.   */
  128. bool testCase = false;
  129. int numTest = 1;
  130. // cin >> numTest;
  131. forw (i, 1, numTest) {
  132. if (testCase) cout << "Case " << i << ": ";
  133. solve();
  134. }
  135. return 0;
  136. }
  137.  
  138. /*
  139.   /\__/\
  140.  (=^.^= )
  141.  (") (")_/
  142. */
  143.  
Success #stdin #stdout 0.01s 5320KB
stdin
9
stdout
7