import sys
input = sys.stdin.readline
from math import sqrt,ceil
sieve = [1]*1000002
sieve[0] = sieve[1] = 0
prime = []
for i in range(2,1000002):
if sieve[i]==0:
continue
prime.append(i)
if i>1000:
continue
n = 2
while i*n<=1000001:
sieve[i*n] = 0
n += 1
min,max = map(int,input().split())
check = {i:1 for i in range(min,max+1)}
cnt = max-min+1
for p in prime:
p = p**2
n = ceil(min/p)
while p*n<=max:
if check[p*n]:
check[p*n] = 0
cnt -= 1
n += 1
print(cnt)
간단한 문제인데 시간복잡도를 잘못 생각해서 뻘짓한 문제이다.
사실 풀이는 문제 보자마자 떠올랐는데, 압도적인 숫자범위 앞에서 (숫자크기 1조, 범위 100만) 당연히 이 풀이는 아닐거라고 생각하고 다른 방법 찾는다고 고민고민하다가 그냥 제출해봤더니 맞았다.
알고리즘을 요약하면 이러하다.
1. 숫자의 범위가 최대 1조이므로, 소수를 100만범위까지 구해준다. (100만의 제곱이 1조이므로)
2. 소수는 에라토스테네스의 체 방식으로 구하며, 이때 for문은 1000까지만 돌린다 (1000의 제곱이 100만이므로)
3. 각 소수의 제곱수에 대해서 에라토스테네스의 체 방식으로 min부터 max까지 제곱수의 배수를 걸러준다.
시간복잡도에 대해서 아직 익숙지 않은 부분이 많다는걸 알려주는 문제였다.
오늘의 교훈) 시간복잡도에 대해서 더 정확하게 판단하자