結果

問題 No.3127 Multiple of Twin Prime
コンテスト
ユーザー shimaaa
提出日時 2025-04-25 22:44:18
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 341 ms / 2,500 ms
コード長 1,474 bytes
コンパイル時間 3,285 ms
コンパイル使用メモリ 280,472 KB
実行使用メモリ 14,060 KB
最終ジャッジ日時 2025-04-25 22:44:28
合計ジャッジ時間 8,061 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using LI = long long int;
using LD = long double;
using namespace std;
template <typename T>
using APQUE = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
using DPQUE = priority_queue<T>;

std::vector<long long> Eratosthenes(const long long N) {
    std::vector<bool> is_prime(N + 1);
    for (long long i = 0; i <= N; i++) {
        is_prime[i] = true;
    }
    std::vector<long long> P;
    for (long long i = 2; i <= N; i++) {
        if (is_prime[i]) {
            for (long long j = 2 * i; j <= N; j += i) {
                is_prime[j] = false;
            }
            P.emplace_back(i);
        }
    }
    return P;
}

int main() {
    vector<long long> primelist = Eratosthenes(10000100);
    vector<long long> productlist;
    for (long long i = 0; i < primelist.size() - 1; i++) {
        if (primelist[i + 1] - primelist[i] == 2) {
            productlist.push_back(primelist[i] * primelist[i + 1]);
        }
    }

    long long t;
    cin >> t;
    rep(i, t) {
        long long n;
        cin >> n;
        if (n < 15) {
            cout << "-1" << endl;
            continue;
        }
        auto it = upper_bound(productlist.begin(), productlist.end(), n);
        if (it == productlist.begin()) {
            cout << "-1" << endl;
            continue;
        }
        cout << *(upper_bound(productlist.begin(), productlist.end(), n) - 1) << endl;
    }
}
0