Tag: sieve of eratosthenes

• 1 ≤ min ≤ 1,000,000,000,000
• min ≤ max ≤ min + 1,000,000

2부터 증가하면서 제곱 수의 배수들을 빼주는 식으로 제곱 ㄴㄴ 수를 찾아가는 방식으로 문제를 해결하려 다음과 같이 시도하였다.

n, m = map(int, input().split())
sqr = [False] * (m - n + 1)
cnt = 0
for i in range(2, int(m ** 0.5) + 1):
    j = 1
    sqr_num = i ** 2
    while sqr_num * j <= m:
        if sqr_num * j < n: pass
        elif not sqr[sqr_num * j - n]:
            sqr[sqr_num * j - n] = True
            cnt += 1
        j += 1
print((m - n + 1) - cnt)