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;
    }
  }
}