백준 1016

문제

어떤 수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min과 max를 포함한 사이에 제곱ㄴㄴ수가 몇 개 있는지 출력한다.

입력

첫째 줄에 두 정수 min과 max가 주어진다.

출력

첫째 줄에 [min,max]구간에 제곱ㄴㄴ수가 몇 개인지 출력한다.

 

해결방안

해당 방식은 에라토스테네스의 채 방식을 사용하였다. boolean list를 사용하엿으며 제곱수에 나눠 지는 수를 모두 false 로 두어 해결하고자 하였다. 

min , mx = map(int,input().split())
check = [True]*(mx+1-min+1)
check[0] = False

for i in range(2,mx+1):
    a = 0
    cnt = max( min//(i**2),1 )
   a = (i ** 2) * cnt
    while a <= mx:


        if a-min+1 > 0:

            check[a-min+1] = False

        cnt +=1
        a = (i ** 2) * cnt
    if i**2 > mx:
        break



print(sum(check))