結果
問題 | No.1657 Sum is Prime (Easy Version) |
ユーザー | shun2741 |
提出日時 | 2021-08-27 21:39:01 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 571 ms / 2,000 ms |
コード長 | 2,051 bytes |
コンパイル時間 | 4,444 ms |
コンパイル使用メモリ | 269,412 KB |
実行使用メモリ | 113,800 KB |
最終ジャッジ日時 | 2023-08-13 08:18:50 |
合計ジャッジ時間 | 9,920 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 69 ms
29,220 KB |
testcase_01 | AC | 70 ms
29,176 KB |
testcase_02 | AC | 509 ms
103,488 KB |
testcase_03 | AC | 70 ms
29,216 KB |
testcase_04 | AC | 70 ms
29,320 KB |
testcase_05 | AC | 70 ms
29,180 KB |
testcase_06 | AC | 71 ms
29,360 KB |
testcase_07 | AC | 71 ms
29,228 KB |
testcase_08 | AC | 71 ms
29,168 KB |
testcase_09 | AC | 72 ms
29,352 KB |
testcase_10 | AC | 70 ms
29,364 KB |
testcase_11 | AC | 74 ms
29,760 KB |
testcase_12 | AC | 476 ms
98,452 KB |
testcase_13 | AC | 251 ms
61,704 KB |
testcase_14 | AC | 290 ms
69,164 KB |
testcase_15 | AC | 351 ms
79,380 KB |
testcase_16 | AC | 152 ms
45,192 KB |
testcase_17 | AC | 82 ms
31,684 KB |
testcase_18 | AC | 105 ms
35,780 KB |
testcase_19 | AC | 505 ms
103,200 KB |
testcase_20 | AC | 196 ms
52,472 KB |
testcase_21 | AC | 571 ms
113,800 KB |
testcase_22 | AC | 70 ms
29,368 KB |
testcase_23 | AC | 121 ms
38,192 KB |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; // デバッグ表示 #define dump(x) cout << #x << ":" << (x) << endl; // 型定義 typedef long long ll; typedef pair<ll, ll> P; // forループ #define REP(i,n) for(ll i=0; i<(ll)(n); ++i) // 定数宣言 const int INF = 1e9; const int MOD = 1e9+7; const ll LINF = 1e18; // modint using mint = modint1000000007; // using mint = modint998244353; // グラフ表現 using Graph = vector<vector<int>>; // グラフの辺表現 using Edge = map<pair<int,int>,int>; // n次元配列の初期化。第2引数の型のサイズごとに初期化していく。 template<typename A, size_t N, typename T> void Fill(A (&array)[N], const T &val){ std::fill( (T*)array, (T*)(array+N), val ); } // コンビネーションを計算する関数 ll pow(ll N, ll k) { ll res = 1; for (ll i = 0; i < k; ++i) res *= N; return res; } // 最大公約数 ll gcd(ll a,ll b){ if (a%b == 0) return(b); else return(gcd(b, a%b)); } // 最小公倍数 ll lcm(ll a, ll b){ return a/gcd(a, b) * b; } bool prime_check(ll n) { if(n == 1) return false; for(ll i = 2; i * i <= n; i++) { while(n % i == 0) { return false; } } return true; } ll N; ll arr[2000010]; vector<ll> prime; void Eratosthenes(){ for(int i = 0; i < N; i++){ arr[i] = 1; } for(int i = 2; i < sqrt(N); i++){ if(arr[i]){ for(int j = 0; i * (j + 2) < N; j++){ arr[i *(j + 2)] = 0; } } } for(int i = 2; i < N; i++){ if(arr[i]){ //cout << i << endl; prime.push_back(i); } } } int main() { cout << fixed << setprecision(15); ll L, R; cin >> L >> R; N = 2000010; Eratosthenes(); map<ll,ll> M; for(auto v: prime){ // cout << v << endl; M[v] = 1; } // cout << prime.size() << endl; ll ans = 0; for(ll i=L; i<=R; i++){ if(M[i] == 1) ans++; if(i == R) break; if(M[2*i+1] == 1) ans++; } cout << ans << endl; return 0; }