結果

問題 No.3127 Multiple of Twin Prime
コンテスト
ユーザー hiromi_ayase
提出日時 2025-04-26 02:15:26
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 281 ms / 2,500 ms
コード長 1,374 bytes
コンパイル時間 6,044 ms
コンパイル使用メモリ 333,632 KB
実行使用メモリ 10,540 KB
最終ジャッジ日時 2025-04-26 02:15:37
合計ジャッジ時間 10,871 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#include <atcoder/all>
using namespace std;
using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
#define FAST_IO                \
  ios::sync_with_stdio(false); \
  cin.tie(0);
const i64 INF = 1001001001001001001;
using Modint = atcoder::static_modint<998244353>;

vector<int> get_primes(int n) {
  vector<int> res;
  vector<bool> is_prime(n + 1, true);
  for (int i = 2; i <= n; i ++) {
    if (is_prime[i]) {
      res.push_back(i);
      for (int j = i + i; j <= n; j += i) {
        is_prime[j] = false;
      }
    }
  }
  return res;
}

vector<pair<i64, i64>> twin_primes(int n) {
  vector<pair<i64, i64>> res;
  vector<int> primes = get_primes(n);
  for (int i = 0; i < primes.size() - 1; i ++) {
    if (primes[i + 1] - primes[i] == 2) {
      res.emplace_back(primes[i], primes[i + 1]);
    }
  }
  return res;
}

int main() {
  FAST_IO

  auto tp = twin_primes(1e7 + 1000);


  int T;
  cin >> T;
  for (int i = 0; i < T; i ++) {
    i64 N;
    cin >> N;

    int ok = -1;
    int ng = tp.size();
    while (ng - ok > 1) {
      int mid = (ok + ng) / 2;
      if (tp[mid].first * tp[mid].second <= N) {
        ok = mid;
      } else {
        ng = mid;
      }
    }
    if (ok == -1) {
      cout << -1 << endl;
      continue;
    }
    cout << tp[ok].first * tp[ok].second << endl;
  }

}
0