結果
問題 | No.732 3PrimeCounting |
ユーザー |
![]() |
提出日時 | 2018-09-07 22:37:55 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2,085 ms / 3,000 ms |
コード長 | 660 bytes |
コンパイル時間 | 175 ms |
コンパイル使用メモリ | 30,336 KB |
実行使用メモリ | 7,808 KB |
最終ジャッジ日時 | 2024-11-29 16:13:19 |
合計ジャッジ時間 | 41,045 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 89 |
ソースコード
#include <stdio.h> int pr[300001]; int prs[26000]; int ptr; long long dp[4][300000]; int main(void) { int n; scanf("%d", &n); for (int i = 2; i <= 300000; i++) { if (!pr[i]) { prs[ptr++] = i; for (int j = i * 2; j <= 300000; j += i) { pr[j] = 1; } } pr[i] = !pr[i]; } dp[0][0] = 1; for (int k = 0; prs[k] <= n; k++) { for (int i = 2; i >= 0; i--) { for (int j = 0; j <= 100000 * i; j++) { dp[i + 1][prs[k] + j] += dp[i][j]; } } } long long ans = 0; for (int i = 0; i < 300000; i++) { if (pr[i]) { ans += dp[3][i]; } } printf("%lld\n", ans); return 0; }