Jinho Tech

난이도가 있는(시간 초과) 수학 문제이다. 0부터 시작해서 제곱 값들을 확인하면

무조건 시간 초과가 나오기 때문에 a보다 크거나 같은 제곱수들만 확인해야 한다. 

a, b = map(int, input().split())
li = [1]*(b-a+1)
for i in range(2, int(b**0.5)+1):
    t = i**2
    for j in range(a//t*t, b+1, t):
        if j-a >= 0 and li[j-a]:
            li[j-a] = 0
print(li.count(1))