結果
問題 |
No.732 3PrimeCounting
|
ユーザー |
![]() |
提出日時 | 2019-04-30 16:44:11 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 250 ms / 3,000 ms |
コード長 | 774 bytes |
コンパイル時間 | 942 ms |
コンパイル使用メモリ | 31,488 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-30 09:47:02 |
合計ジャッジ時間 | 5,595 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 89 |
ソースコード
// yukicoder: No.732 3PrimeCounting // 2019.4.30 bal4u #include <stdio.h> #include <math.h> #define MAX 300005 char notPrime[MAX] = { 1,1,0,0,1 }; // zero: if prime int ptbl[26000] = { 2 }; int sz; // 25997 void sieve(int n) { int i, j, b; b = (int)sqrt((double)n); for (i = 3; i <= b; i += 2) { if (!notPrime[i]) { for (j = i * i; j <= n; j += i) notPrime[j] = 1; } } sz = 1; for (i = 3; i <= n; i += 2) { if (!notPrime[i]) ptbl[sz++] = i; } } int f[300005]; int main() { int N, i, a, b, c, d; long long ans; scanf("%d", &N); sieve(3*N); ans = 0; for (i = 3; (c = ptbl[i]) <= N; i++) { b = ptbl[i-1]; for (a = 1; a < i-1; a++) f[ptbl[a] + b]++; for (d = i+1; d < sz; d++) ans += f[ptbl[d]-c]; } printf("%lld\n", ans); return 0; }