yukicoder No.371 ぼく悪いプライムじゃないよ
解法
必要な素数をエラトステネスのふるいで全列挙しておく。
列挙した素数を大きい方から見ていき、その素数が解答の最小の素因数になりうるかを考える。
見ている素数をprime[i]とするとき、[L, H] に含まれるprime[i]の倍数のうち、prime[i]が最小の素因数となる数を探したい。
- [L, H] の区間で、調べるべき区間は [max(L, prime[i]^2, H] である。
- [L, H] に含まれる prime[i] の倍数の個数は全部で (H-L+1)/prime[i] 個
- ところで prime[j+1]^2 と prime[j] の間の個数はたかだか10^5個くらいなので、10^5個くらい調べれば素数の2乗に当たる。
- よってprime[i+1] が最小の素因数となるような数が含まれていない区間[L, H] で調べるべきprime[i]の倍数を全て列挙しても大した数にならない。
コード
#include <bits/stdc++.h> using namespace std; vector<int> primes; // エラトステネスの篩 void eratosthenes(int N) { vector<bool> is_prime(N + 1, true); is_prime[0] = false; is_prime[1] = false; for (int i = 2; i <= N; ++i) if (is_prime[i]) { primes.push_back(i); for (int j = i * 2; j <= N; j += i) { is_prime[j] = false; } } } int64_t get_min_divisor(int64_t t) { for (int p : primes) if (t % p == 0) return p; else if (p > sqrt(t + 1)) break; return t; } int main() { cin.tie(0); ios::sync_with_stdio(false); eratosthenes(1e5); int64_t L, H; cin >> L >> H; for (int i = primes.size() - 1; i >= 0; --i) { int64_t prime = primes[i]; int64_t h = H / prime * prime; int64_t l = max(L, prime * prime); for (; h >= l; h -= prime) { int64_t divisor = get_min_divisor(h / prime); if (divisor < prime) { continue; } cerr << prime << endl; cout << h << endl; return 0; } } }