結果

問題 No.1657 Sum is Prime (Easy Version)
コンテスト
ユーザー lam6er
提出日時 2025-03-20 18:46:07
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 214 ms / 2,000 ms
コード長 1,100 bytes
コンパイル時間 137 ms
コンパイル使用メモリ 82,180 KB
実行使用メモリ 155,124 KB
最終ジャッジ日時 2025-03-20 18:46:20
合計ジャッジ時間 3,560 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def count_primes_in_range(primes, a, b):
    left = bisect.bisect_left(primes, a)
    right = bisect.bisect_right(primes, b)
    return right - left

def main():
    import sys
    input = sys.stdin.read().split()
    L = int(input[0])
    R = int(input[1])
    
    max_limit = 2 * R
    sieve_size = max(max_limit, 3)  # Ensure at least up to 2R
    
    # Sieve of Eratosthenes
    sieve = [True] * (sieve_size + 1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(sieve_size ** 0.5) + 1):
        if sieve[i]:
            sieve[i*i : sieve_size+1 : i] = [False] * len(sieve[i*i : sieve_size+1 : i])
    primes = [i for i, is_p in enumerate(sieve) if is_p]
    
    # Case 1: primes p where L <= p <= R
    count1 = count_primes_in_range(primes, L, R)
    
    # Case 2: primes p where 2L + 1 <= p <= 2R - 1 and p is odd (>=3)
    start = max(2 * L + 1, 3)
    end = 2 * R - 1
    if start > end:
        count2 = 0
    else:
        count2 = count_primes_in_range(primes, start, end)
    
    total = count1 + count2
    print(total)

if __name__ == "__main__":
    main()
0