結果
問題 |
No.3127 Multiple of Twin Prime
|
ユーザー |
|
提出日時 | 2025-04-26 04:44:02 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 280 ms / 2,500 ms |
コード長 | 1,104 bytes |
コンパイル時間 | 1,300 ms |
コンパイル使用メモリ | 96,536 KB |
実行使用メモリ | 7,844 KB |
最終ジャッジ日時 | 2025-04-26 04:44:08 |
合計ジャッジ時間 | 5,918 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 12 |
ソースコード
#include <iostream> #include <vector> #include <cmath> #include <algorithm> using namespace std; using ll = long long; const ll MAX = 1e7; vector<bool> sieve(MAX + 1, true); vector<ll> L; int main() { sieve[0] = sieve[1] = false; for (ll i = 2; i <= sqrt(MAX); ++i) { if (sieve[i]) { for (ll j = i * i; j <= MAX; j += i) { sieve[j] = false; } } } // Lを作る: 素数pで、p+2も素数であるものを保存 for (ll i = 2; i <= MAX - 2; ++i) { if (sieve[i] && sieve[i + 2]) { L.push_back(i); } } ll T; cin >> T; while (T--) { ll N; cin >> N; ll rootN = sqrt(N); auto it = upper_bound(L.begin(), L.end(), rootN); if (it != L.begin()) --it; // upper_boundなので一つ前に戻す while (it != L.begin() && (*it) * (*it + 2) > N) { --it; } if ((*it) * (*it + 2) > N) { cout << -1 << endl; } else { cout << (*it) * (*it + 2) << endl; } } return 0; }