結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff #

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)
0