結果
問題 | No.1657 Sum is Prime (Easy Version) |
ユーザー | shun2741 |
提出日時 | 2021-08-27 21:39:01 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 559 ms / 2,000 ms |
コード長 | 2,051 bytes |
コンパイル時間 | 4,517 ms |
コンパイル使用メモリ | 270,816 KB |
実行使用メモリ | 113,876 KB |
最終ジャッジ日時 | 2024-05-01 01:59:07 |
合計ジャッジ時間 | 9,552 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 74 ms
29,268 KB |
testcase_01 | AC | 69 ms
29,272 KB |
testcase_02 | AC | 502 ms
103,764 KB |
testcase_03 | AC | 70 ms
29,268 KB |
testcase_04 | AC | 67 ms
29,392 KB |
testcase_05 | AC | 68 ms
29,268 KB |
testcase_06 | AC | 69 ms
29,524 KB |
testcase_07 | AC | 73 ms
29,400 KB |
testcase_08 | AC | 69 ms
29,524 KB |
testcase_09 | AC | 73 ms
29,396 KB |
testcase_10 | AC | 67 ms
29,524 KB |
testcase_11 | AC | 71 ms
29,908 KB |
testcase_12 | AC | 467 ms
98,520 KB |
testcase_13 | AC | 247 ms
61,908 KB |
testcase_14 | AC | 283 ms
69,332 KB |
testcase_15 | AC | 346 ms
79,700 KB |
testcase_16 | AC | 150 ms
45,140 KB |
testcase_17 | AC | 83 ms
31,952 KB |
testcase_18 | AC | 105 ms
36,048 KB |
testcase_19 | AC | 498 ms
103,380 KB |
testcase_20 | AC | 189 ms
52,436 KB |
testcase_21 | AC | 559 ms
113,876 KB |
testcase_22 | AC | 72 ms
29,400 KB |
testcase_23 | AC | 123 ms
38,356 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; }