クルトンのプログラミング教室

Pythonの使い方やPythonを使った競技プログラミングの解法などを解説しています。

Pythonで理解する蟻本「2-6 区間内の素数の個数」(p.113)

Pythonで理解する蟻本（プログラミングコンテストチャレンジブック）

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「2-6 区間内の素数の個数」(p.113)
のコードをPythonで書き直したものとなっています。

入力


a\,b

入力例



22801763489 22801787297

解答

MAX_L = 10 ** 6
MAX_SQRT_B = 10 ** 6

is_prime = [True] * MAX_L
is_prime_small = [True] * MAX_SQRT_B

# [a,b)の整数に対して篩を行う。is_prime[i - a] = True ⇔ iが素数
def segment_sieve(a, b):
    i = 0
    while i * i < b:
        is_prime_small[i] = True
        i += 1
    i = 0
    for i in range(b - a):
        is_prime[i] = True
    
    i = 2
    while i * i < b:
        if is_prime_small[i]:
            j = 2 * i
            while j * j < b:
                is_prime_small[j] = False    # [2,√b)の篩
                j += i
            j = (a + i - 1) // i * i
            while j < b:
                is_prime[j - a] = False    # [a,b)の篩
                j += i
        i += 1

a, b = map(int,input().split())
segment_sieve(a, b)
ans = sum(is_prime[:b - a])
print(ans)