행복한 삶을 찾아서

에라토스테네스고 뭐시기고 필요없다. set() 자료형으로 쉽게 해결.

주어진 수 범위에서 제곱수로 나누어 떨어지는 수의 개수를 뺐다. 주어진 수 범위를 반복문으로 돌면 시간초과.

주어진 예제 입력 외에도 최소/최대 조합인 [1,000,000,000,000, 1,000,001,000,000] 범위로 테스트 해보기. [4, 4] 범위도 0 나오는지 잘 확인해보기

min_num, max_num = map(int, input().split(" "))
# 2 부터 (max의 제곱근 정수부분) 까지 반복문을 돌려서 검사하면?
max_sqrt = int(max_num**0.5)
# min_num보다 크거나 같고 max_num보다 작거나 같은 수 중에서
# 제곱수로 나누어 떨어지는 수를 리스트에 집어넣고 set으로 변환
num_list = []
for a in range(2, max_sqrt+1):
	if a != 1:
		square_a = a*a
		Q_min = min_num//square_a
		Q_max = max_num//square_a
		
		for b in range(max(Q_min,1), Q_max+1):
			if square_a*b >= min_num and square_a*b <= max_num:
				num_list.append(square_a*b)

num_set = set(num_list)
print(max_num-min_num+1-len(num_set))