結果

問題 No.3127 Multiple of Twin Prime
コンテスト
ユーザー Iroha_3856
提出日時 2025-03-10 13:44:35
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 306 ms / 2,500 ms
コード長 919 bytes
コンパイル時間 3,478 ms
コンパイル使用メモリ 279,932 KB
実行使用メモリ 7,324 KB
最終ジャッジ日時 2025-03-10 13:44:43
合計ジャッジ時間 7,485 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define rep(i, l, r) for (int i = (int)(l); i<(int)(r); i++)
#define ll long long

//エラトステネスの篩による [1, N] の素数判定
vector<bool> primeSieve(int N) {
    vector<bool> isPrime(N+1, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i <= N; i++) {
        if (isPrime[i]) {
            for (int j = 2*i; j <= N; j += i) isPrime[j] = false;
        }
    }
    return isPrime;
}

int main() {
    int B = 10'000'000;
    vector<bool> isprime = primeSieve(B);
    vector<ll> P;
    rep(i, 0, B-1) {
        if (isprime[i] and isprime[i+2]) {
            P.push_back((ll)i*(i+2));
        }
    }
    int T; cin >> T;
    while(T--) {
        ll x; cin >> x;
        auto itr = upper_bound(P.begin(), P.end(), x);
        if (itr == P.begin()) {
            cout << -1 << endl;
        }
        else cout << *prev(itr) << endl;
    }
}
0