結果
| 問題 | No.1661 Sum is Prime (Hard Version) |
| ユーザー |
 Viet Phan
|
| 提出日時 | 2024-11-13 11:16:17 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 1,139 bytes |
| コンパイル時間 | 925 ms |
| コンパイル使用メモリ | 69,120 KB |
| 実行使用メモリ | 817,664 KB |
| 最終ジャッジ日時 | 2024-11-13 11:16:21 |
| 合計ジャッジ時間 | 3,233 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | AC | 2 ms
5,248 KB |
| testcase_02 | MLE | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
ソースコード
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
// Hàm sàng Eratosthenes để tìm các số nguyên tố đến max_val
vector<bool> sieve(ll max_val) {
vector<bool> is_prime(max_val + 1, true);
is_prime[0] = is_prime[1] = false;
for (ll i = 2; i * i <= max_val; ++i) {
if (is_prime[i]) {
for (ll j = i * i; j <= max_val; j += i) {
is_prime[j] = false;
}
}
}
return is_prime;
}
int count_prime_sums(ll L, ll R) {
ll max_val = 2 * R + 1;
vector<bool> is_prime = sieve(max_val);
int count = 0;
// Đếm số nguyên tố trong khoảng [L, R] (trường hợp k = 0)
for (ll A = L; A <= R; ++A) {
if (is_prime[A]) count++;
}
// Kiểm tra 2A + 1 có là số nguyên tố (trường hợp k = 1)
for (ll A = L; A < R; ++A) {
ll candidate = 2 * A + 1;
if (candidate <= max_val && is_prime[candidate]) {
count++;
}
}
return count;
}
int main() {
ll L, R;
cin >> L >> R;
cout << count_prime_sums(L, R) << endl;
return 0;
}