結果
問題 |
No.732 3PrimeCounting
|
ユーザー |
![]() |
提出日時 | 2025-08-11 17:52:24 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,150 ms / 3,000 ms |
コード長 | 844 bytes |
コンパイル時間 | 288 ms |
コンパイル使用メモリ | 82,116 KB |
実行使用メモリ | 91,120 KB |
最終ジャッジ日時 | 2025-08-11 17:52:55 |
合計ジャッジ時間 | 29,603 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 89 |
ソースコード
from collections import defaultdict N = int(input()) array = [1]*(3*N+1) array[0] = 0 array[1] = 0 prime_1 = [] prime_2 = [] i = 2 while i <= 3*N: if array[i]: for j in range(2*i, 3*N+1, i): array[j] = 0 if 3 < i <= N: if i % 3 == 1: prime_1.append(i) elif i % 3 == 2: prime_2.append(i) i += 1 ans = 0 prime_1_1 = defaultdict(int) for i in range(len(prime_1)): for j in range(i+1,len(prime_1)): prime_1_1[prime_1[i]+prime_1[j]] += 1 prime_2_2 = defaultdict(int) for i in range(len(prime_2)): for j in range(i+1,len(prime_2)): prime_2_2[prime_2[i]+prime_2[j]] += 1 for s in prime_1_1: c = array[3+s] for j in prime_2: c += array[j+s] ans += c*prime_1_1[s] for s in prime_2_2: c = array[3+s] for j in prime_1: c += array[j+s] ans += c*prime_2_2[s] print(ans)