結果

問題 No.843 Triple Primes
ユーザー lam6er
提出日時 2025-03-20 18:51:21
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 50 ms / 2,000 ms
コード長 796 bytes
コンパイル時間 142 ms
コンパイル使用メモリ 82,504 KB
実行使用メモリ 63,104 KB
最終ジャッジ日時 2025-03-20 18:52:48
合計ジャッジ時間 3,225 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def count_triple_primes(N):
    if N < 2:
        return 0

    # Sieve of Eratosthenes up to N
    is_prime = [True] * (N + 1)
    is_prime[0], is_prime[1] = False, False
    for i in range(2, int(math.isqrt(N)) + 1):
        if is_prime[i]:
            for j in range(i * i, N + 1, i):
                is_prime[j] = False

    count = 0

    # Check r=2 case
    if N >= 2 and 4 <= 2 * N:
        count += 1

    # Check odd primes r where r^2 <= N + 2
    max_r = math.isqrt(N + 2)
    for r in range(3, max_r + 1, 2):
        if is_prime[r]:
            r_squared = r * r
            q = r_squared - 2
            if q >= 2 and q <= N and is_prime[q]:
                count += 2

    return count

# Read input and output the result
N = int(input())
print(count_triple_primes(N))
0