結果
問題 |
No.732 3PrimeCounting
|
ユーザー |
![]() |
提出日時 | 2020-07-20 12:22:07 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 386 ms / 3,000 ms |
コード長 | 941 bytes |
コンパイル時間 | 2,289 ms |
コンパイル使用メモリ | 198,284 KB |
最終ジャッジ日時 | 2025-01-12 01:15:02 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 89 |
ソースコード
#include <bits/stdc++.h> using namespace std; class Sieve { private: vector<bool> is_pr; vector<int> pr; public: Sieve(int n) : is_pr(n + 1, true) { if (0 < n + 1) is_pr.at(0) = false; if (1 < n + 1) is_pr.at(1) = false; for (int i = 2; i * i <= n; i++) { if (!is_pr.at(i)) continue; for (int j = i * i; j <= n; j += i) is_pr.at(j) = false; } for (int i = 2; i < n + 1; i++) { if (is_pr.at(i)) pr.push_back(i); } } vector<bool> getB() { return is_pr; } vector<int> getP() { return pr; } }; int main() { int N; cin >> N; Sieve S(N * 3); auto P = S.getP(); long ans = 0; vector<int> cnt(N * 3 + 1); for (int c = 0; c < P.size(); c++) { if (P.at(c) > N) break; for (int n = c + 1; n < P.size(); n++) { ans += cnt.at(P.at(n) - P.at(c)); } int b = c; for (int a = 0; a < b; a++) { cnt.at(P.at(a) + P.at(b))++; } } cout << ans << "\n"; }