結果

問題 No.843 Triple Primes
コンテスト
ユーザー AP25
提出日時 2026-06-24 14:29:02
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 143 ms / 2,000 ms
コード長 826 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 915 ms
コンパイル使用メモリ 85,376 KB
実行使用メモリ 74,496 KB
最終ジャッジ日時 2026-06-24 14:29:15
合計ジャッジ時間 11,619 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# 5 * 10 ** 5 以下の素数　41538
# r** 2 <= 10 ** 6となる素数rの数168
# r x pで全探索qは素数集合に含まれるかで判定

def eratos(n):
    primes = [True] * (n+1)
    primes[0], primes[1] = False, False
    for i in range(2, int(n**0.5)+1):
        if primes[i]:
            for j in range(i**2, n+1, i):
                primes[j] = False
    ret = [num for num, is_prime in enumerate(primes) if is_prime]
    return ret

prime = eratos(5 * 10 ** 5 +1)

N = int(input())

pr2 = []
for e in prime:
    t = e * e
    if t > N + N:
        break
    pr2.append(t)

g_prime = set(prime)

ans = 0
for r2 in pr2:
    for p in prime:
        q = r2 - p
        if p > N or q <= 1:
            break

        if q <= N and q in g_prime:
            ans += 1

print(ans)
0