結果
問題 |
No.732 3PrimeCounting
|
ユーザー |
![]() |
提出日時 | 2020-03-08 10:04:03 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 178 ms / 3,000 ms |
コード長 | 852 bytes |
コンパイル時間 | 659 ms |
コンパイル使用メモリ | 73,704 KB |
実行使用メモリ | 5,888 KB |
最終ジャッジ日時 | 2024-11-06 20:11:11 |
合計ジャッジ時間 | 5,240 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 89 |
ソースコード
#include <algorithm> #include <iostream> #include <vector> #include <numeric> using namespace std; vector<int> prime_table(int n) { vector<int> is_prime(n + 1); if (n) iota(is_prime.begin() + 2, is_prime.end(), 2); for (int i = 2; i * i <= n; i++) if (is_prime[i]) { for (int j = i + i; j <= n; j += i) is_prime[j] = 0; } return is_prime; } vector<int> make_primes(int ma) { vector<int> ps = prime_table(ma); ps.erase(remove(ps.begin(), ps.end(), 0), ps.end()); return ps; } int main() { int n; cin >> n; auto ps = make_primes(n * 4); long long res = 0; vector<int> cnt(n * 3); for (int c = 2; ps[c] <= n; c++) { for (int a = 0, b = c - 1; a < b; a++) cnt[ps[a] + ps[b]]++; for (int s = c + 1; ps[s] < ps[c] * 3; s++) res += cnt[ps[s] - ps[c]]; } cout << res << endl; return 0; }