結果
問題 |
No.732 3PrimeCounting
|
ユーザー |
|
提出日時 | 2022-02-23 18:17:26 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,646 ms / 3,000 ms |
コード長 | 937 bytes |
コンパイル時間 | 157 ms |
コンパイル使用メモリ | 82,944 KB |
実行使用メモリ | 86,784 KB |
最終ジャッジ日時 | 2024-07-01 18:42:46 |
合計ジャッジ時間 | 34,333 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 89 |
ソースコード
N = int(input()) p1 = [] p2 = [] p = set() C = 3 * N+1 dat = [0] * C for i in range(2,C,2): dat[i] = 1 for i in range(3,C): if dat[i] == 0: if i <= N: if i % 3 == 1: p1.append(i) elif i % 3 == 2: p2.append(i) p.add(i) for j in range(i * 2,C,i): dat[j] = 1 dat = [0] * (2 * N) for i in range(len(p1)): for j in range(i + 1,len(p1)): dat[p1[i]+p1[j]] += 1 dat2 = [0] * C for i in p2: for j in range(20,2 * N,3): dat2[j+i] += dat[j] for j in range(20,2 * N,3): dat2[j+3] += dat[j] ans = 0 for v in p: ans += dat2[v] dat = [0] * (2 * N) dat2 = [0] * C for i in range(len(p2)): for j in range(i + 1,len(p2)): dat[p2[i]+p2[j]] += 1 for i in p1: for j in range(16,2 * N,3): dat2[i+j] += dat[j] for j in range(16,2 * N,3): dat2[j+3] += dat[j] for v in p: ans += dat2[v] print(ans)