백준 1016 제곱ㄴㄴ수

특정 범위의 수가 제곱수로 나누어 지는지 확인하는 문제이다.
이 문제의 특징은 left의 범위가 1조라는 것이다.
하지만 right는 1조+1백만까지이므로 1백만 사이의 숫자들 중에서 어떤것을 고를지를 고민하면 된다.
물론 1조크기의 배열을 만드는것은 말이 안되고,
에라토네스의 체를 이용해 제곱수로 나누어 떨어지는 것을 거르고, 값의 범위인 1백만을 배열의 처음부터 인덱스를 지정해주면 된다.

그러기 위해선 left값 이상인 가장 큰 제곱수를 찾고, 그 제곱수의 배수를 에라토네스의 체를 이용해 거르고, 그 제곱수의 원래 수를 1 올린뒤, 다시 에라토네스의 체를 이용해 거르면 된다.
제곱수가 어느 순간 right값을 넘어서는 순간에 로직을 끝내주면 된다.

a,b = map(int,input().split())
arr = [0] * (b-a+1)
i = 2
ans = b-a+1
while i*i <= b:
    k = i*i
    remain = 0 if a % k == 0 else 1
    j = a // k + remain
    while k*j <= b:
        if not arr[k*j-a]:
            arr[k*j-a] = 1
            ans -= 1
        j += 1
    i += 1
print(ans)