結果

問題 No.3127 Multiple of Twin Prime
ユーザー startcpp
提出日時 2025-04-25 22:17:56
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 302 ms / 2,500 ms
コード長 895 bytes
コンパイル時間 998 ms
コンパイル使用メモリ 67,536 KB
実行使用メモリ 13,676 KB
最終ジャッジ日時 2025-04-25 22:18:02
合計ジャッジ時間 5,166 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

// ルートまで探索するテクテク。クエリは二分探索すればおっけー。
#include <iostream>
#include <vector>
#define rep(i, n) for(i = 0; i < n; i++)
#define int long long
using namespace std;

const int MAX = 10000010;
bool isprime[MAX];
vector<int> aoi;

signed main() {
	int i, j;

	for (i = 2; i < MAX; i++) isprime[i] = true;
	for (i = 2; i < MAX; i++) {
		if (isprime[i]) {
			for (j = 2 * i; j < MAX; j += i) {
				isprime[j] = false;
			}
		}
	}

	for (i = 2; i < MAX - 2; i++) {
		if (isprime[i] && isprime[i + 2]) {
			aoi.push_back(i);
		}
	}

	int q; cin >> q;
	while(q--) {
		int n;
		cin >> n;

		int ok = -1, ng = aoi.size(), mid;
		while (ng - ok >= 2) {
			mid = (ok + ng) / 2;
			if (aoi[mid] * (aoi[mid] + 2) <= n) ok = mid;
			else ng = mid;
		}

		if (ok >= 0) {
			cout << aoi[ok] * (aoi[ok] + 2) << endl;
		}
		else {
			cout << -1 << endl;
		}
	}
}
0