蟻本 2-6 区間内の素数の個数

code: python

MAX_L = 10 ** 6

MAX_SQRT_B = 10 ** 6

is_prime = True * MAX_L

is_prime_small = True * MAX_SQRT_B

# [a,√b)の表と[a,b)の表を別々に作っておいて、[2,√b)の表から素数が得られるたびに、その素数の倍数を[a,b)から除けば[a, b)にある素数が列挙できる

def segment_sieve(a, b):

i = 0

while i * i < b:

is_prime_smalli = True

i += 1

i = 0

for i in range(b - a):

is_primei = True

i = 2

while i * i < b:

if is_prime_smalli:

j = 2 * i

while j * j < b:

is_prime_smallj = False # [2,√b)の篩

j += i

j = (a + i - 1) // i * i

while j < b:

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