[Python] 1016번 : 제곱ㄴㄴ수

 

https://www.acmicpc.net/problem/1016

1016번: 제곱 ㄴㄴ 수

 

문제 3줄 요약

1. 1보다 큰 제곱수(2, 4, ..)로 나누어 떨어지지 않는 수가 있다.

2. 그 수를 제곱ㄴㄴ수라고 한다.

3. 주어진 두 정수 사이의 제곱ㄴㄴ수가 몇 개 있는지 출력!

 

 

---

 

문제 이름이 제곱ㄴㄴ수 이기 때문에

제곱이 중요한 문제처럼 보이지만

저번에 풀었던 환상의 짝꿍과 마찬가지로 소수와 관련된 문제이다.

 

왜 소수랑 관련이 있을까?

 

차근차근 알아보자!

 

 

 

제곱수에는 다음과 같은 수들이 있을 것이다.

 

 

문제에서는 제곱수로 나누어 떨어지지 않는 수를 찾는다.

그렇단 이야기는

제곱수로 나눠서 나머지가 있다는 뜻인데..

 

36으로 나누어 떨어지는 수와 16으로 나누어 떨어지는 수는

4로 나누었을 때,

모두 나머지가 없을 것이다.

 

즉, 제곱수 중 4의 배수인 16, 36 같은 경우는

나눠줄 리스트에서 제외시켜도 된다는 뜻!

 

포함시켜서 반복문을 돌리면

시간 초과가 생기게 된다.

 

---

 

그렇다면,

제곱수이면서, 다른 제곱수의 배수가 아닌 수는?

 

 

소수의 제곱수가 되겠다!

 

따라서 앞서 언급했던 것처럼

제곱이 메인이 아닌 소수의 제곱이 중요한 문제였다.

 

 

소수를 구하는 문제이기에

늘 그랬듯이 에라토스테네스의 체를 사용하여,

min과 max 사이의 소수를 계산하고 제출하니..

 

 

1%를 벗어나지 못했다.

 

오늘도 질문게시판을 서성이던 나는

힌트를 보게 되었다.

 

" min과 max 사이의 최초 소수를 O(1) 시간복잡도로 찾을 수 있다. "

 

이게 무슨 소리여?

 

노트를 펴고 나눗셈을 하다보니 하나 깨닫게 되었다.

 

100 ~ 200 사이에서 처음으로 등장하는 9의 배수는 몇 일까?

 

가장 간단한 방법은

100 ÷ 9를 한 후, 나머지가 있다면 

몫인 (11+1) * 나눈 수 9 = 108.

 

 없는 경우인

100 ÷ 4 에서는

몫 25 * 나눈 수 4 = 100.

 

위와 같이 구할 수 있다.

이를 이용하여 범위 안에서 첫 4로 나누어 떨어지는 소수를 찾는다면?

 

100, 104, 108, 112 ... 4씩 차이가 나는 수들은

모두 4로 나누어 떨어질 것이다.

 

---

이제 모든 준비는 끝났다..!

 

최대 숫자인 max의 제곱근보다

작은 소수 제곱들을 구한 다음,

min ~ max 사이에서 처음으로 등장하는 소수 제곱으로 나누어 떨어지는 수에

소수 제곱만큼 차이나는 수들을 제외한다.

 

그렇다면 남은 수들은

제곱수로 나누어 떨어지지 않는 숫자들..!

 

 

from sys import stdin

min, max = map(int,stdin.readline().split())

# limit : max의 제곱근
# num_set : 소수 제곱으로 나누어 떨어지는 수
limit = int(max**0.5)
num_set = set()

for i in range(2, limit+1):
	# min ~ max 사이의 첫 소수제곱으로 나누어떨어지는 수 찾기
    roop = (min//i**2)*(i**2)
    if roop < min:
        roop += i**2
    
    # 제외 시키기
    for r in range(roop, max+1, i**2):
        num_set.add(r)

# 1도 포함이므로 +1
print(max-min-(len(num_set))+1)

---

소수 판정 문제..

당분간 그만풀어야겠다.

 

끝!