문제에서 어떤 두 정수 min과 max 사이에 수가 1보다 큰 제곱수로 나누어 떨어지지 않을때 제곱 ㄴㄴ 수 라고 정의를 하였다. 어떤 수가 제곱수로 나누어 떨어지지 않은것을 구하기 위해 우리는 에라토스테네스 방법을 응용할 수 있다. 처음 떠올린 방법은 부르트포스로 생각하였는데 제곱수가 될수 있는 n이 1000000, max-min이 1000000이므로 1000000*1000000 즉 1조가되어 시간초과가 발생한다. 기본적인 에라토스테네스는 소수를 구하기 위해 2,3,5,7의 배수를 모두 지우고 지워지지 않고 남은 수를 우리는 소수임을 알수 있다. 이를 응용하여 i*i (i>1) 가 max 보다 작을때 까지 i*i의 배수를 모두 지워주면 된다. 이때 시작지점은 i*i 가 min 보다는 커야하므로 min/..
