[BOJ/1016] 제곱 ㄴㄴ 수 - 풀이 및 코드

1016번: 제곱 ㄴㄴ 수

문제

풀이

 "제곱 ㄴㄴ수"란, 정수 X의 약수 중 제곱수가 없는 수를 의미합니다.
 어떤 수 K에 제곱수가 존재하는지 존재하지 않는지를 따지기 위해서는 소인수 분해를 진행하면 됩니다. 소인수 분해를 하고 2개 곱해진 소수가 존재하는가?를 확인하면 되기 때문이죠. 어떤 수 K를 나이브하게 소인수 분해하는데에는 O(K)의 시간복잡도가 소요된다고 알려져있습니다. 그러나 문제 조건 중 min값이 최악의 경우 1조이며, max값은 최악의 경우 min보다 백만만큼 크기 때문에 백만개의 숫자를 1조번씩 연산하게 되어 위 방식대로는 풀 수 없습니다. 

 

  저는 이 문제를 풀기 위해 다음과 같이 접근했습니다.우선, 제곱수란 무엇일까요? 어떤 정수를 두번 곱한 것이 제곱수입니다. 어떤 정수는 반드시 소수이거나 합성수일 것입니다(0이나 1이 아님). 만약, 어떤 정수가 합성수라면, 그 제곱수는 소수로 표현할 수 있습니다. 합성수의 정의가 둘 이상의 소수를 곱한 수 이기 때문이죠.

제곱수는 반드시 소수의 제곱수로 표현할 수 있다.

 따라서, 어떤 수 X가 제곱수로 나눠진다면 그 제곱수는 반드시 소수의 제곱수일 것입니다.
문제의 조건에 따르면 최악의 경우, max는 1조 1백만이라는 숫자가 되는데, 그 경우 max의 약수의 후보 중 최대값은 √max입니다.

√max가 소수인 경우도 존재할 수 있기 때문에 2부터 √max까지 존재하는 모든 소수를 구한 뒤, 그렇게 구한 소수들의 제곱수로 min부터 max까지 존재하는 수들을 나누었을 때 나뉘어 떨어지는지 확인하면 됩니다.

 

정리하자면...

1. 2부터 √max 까지에 존재하는 모든 소수를 찾습니다.
2. min부터 max 까지에 존재하는 모든 수에 대해 1번에서 찾은 소수들의 제곱수로 나누어봅니다.

 단, 문제 조건때문에 1번 과정과 2번 과정의 시간복잡도를 낮춰야할 필요가 있습니다. 1번 과정 같은 경우, 특정 수가 소수인지 아닌지 판별하는 것이 아닌, 넓은 범위에 존재하는 소수에는 어떤 것이 있는지 궁금한 것이기 때문에 "에라토스테네스의 체" 기법을 사용합니다. O(N)의 시간복잡도를 가지는 것으로 알려져있습니다. 2번 과정 같은 경우, 모든 수(1백만)를 찾은 소수로 모두 나눠보는 것이 매우 비효율적이기 때문에 "에라토스테네스의 체" 기법과 비슷하게 제곱ㄴㄴ수를 찾습니다.

 

2번 과정의 예시. 모든 수를 제곱수로 나눠보는 것보다 제곱수를 더해나가며 지워나가는 것이 더 효율적이다.

"에라토스테네스의 체" 기법은 시간 복잡도가 O(NloglogN)이고 N값이 √max 이기 때문에 문제 조건에 통과됩니다.

코드

BOJ 코드 치팅은 제재 사유입니다.

 

import math

minimum, maximum = map(int,input().split())

n = int(math.sqrt(maximum))
table = [1 for _ in range(n+1)]
primes = []

for i in range(2, int(math.sqrt(n)) + 1):
    if table[i] == 1:
        for j in range(i + i, n+1, i):
            table[j] = 0

for i in range(2, n+1):
    if table[i]:
        primes.append(i)

ans_sheet = {i: True for i in range(minimum, maximum +1)}
for prime in primes:
    powed = prime * prime
    if powed >= minimum:
        start = powed
    elif minimum % powed == 0:
        start = minimum
    else:
        start = minimum // powed * powed + powed
    
    for i in range(start, maximum + 1, powed):
        ans_sheet[i] = False

cnt = 0
for v in ans_sheet.values():
    if v:
        cnt += 1

print(cnt)

참고자료

Sieve of Eratosthenes - Wikipedia

 

[정수론] 약수 구하기, 소수 판정하기