[🥇1 / 백준 1016 / 파이썬] 제곱 ㄴㄴ 수

 

1016번: 제곱 ㄴㄴ 수

 

문제

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

입력

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

출력

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

제한

• 1 ≤ min ≤ 1,000,000,000,000
• min ≤ max ≤ min + 1,000,000

예제 입력  1 10

예제 출력  7

 

풀이

 

특정 구간에서 제곱수로 나누어 떨어지지 않는 수들을 구하는 문제이다.

 

만약 1 ~ 100 사이의 제곱 ㄴㄴ수를 구하려면 그 사이의 제곱수들을 구해야 한다.

 

제곱수들은 4, 9, 16, 25, 36, 49, 64, 81, 100 이 존재한다.

 

이제 이 수들로 나누어 떨어지지 않는 수를 구해야 한다.

 

4부터 시작하면 4, 8, 12, 16 …

 

9는 9, 18, 27, 36 …

 

이 과정을 짚어보면 생각나는 것이 하나 있는데, 소수를 구할 때 썼던 에라토스테네스의 체이다.

 

먼저 최댓값과 최소값의 범위에 해당하는 길이의 리스트를 만들어 준다.

 

1 ~ 1,000,000,000,000 길이의 리스트를 만들면 쉽겠지만, 메모리 초과에 걸리므로 불가능하다.

 

리스트의 원소 각각의 최초값은 모두 1이며, 이제 제곱수들로 나누어 떨어지는 인덱스들의 값을 0으로 만들어주면 된다.

 

단, 범위가 900,000 ~ 1,000,000 같은 경우 900,000 미만의 제곱수들은 0부터 900,000이 될 때까지 더하며 올라가야 할 것이므로

 

제곱수들의 최초 값이 min 보다 높아지도록 만들어주자.

 

minn, maxx = map(int,input().split())
a = [i**2 for i in range(2,int(maxx**0.5)+1)]
num = [1] * (maxx-minn+1)
for i in a:
    n = minn//i*i
    while(n < maxx+1):
        if n - minn >= 0:
            num[n-minn] = 0
        n += i
print(sum(num))