이 글에서는 주어진 문제를 해결하기 위한 풀이 방법과 접근 방식을 살펴보겠습니다.
문제 정의
문제 — 숫자 n이 주어졌을 때, 해당 숫자의 약수 총 개수가 짝수인지 홀수인지 판별하는 프로그램을 작성합니다.
예를 들어, 100의 약수는 1, 2, 4, 5, 10, 20, 25, 50, 100으로 총 9개이므로 홀수입니다.
접근 방식
1부터 √n까지의 범위에서 n을 나누어 떨어지게 하는 모든 약수를 찾습니다. 핵심 아이디어는 다음과 같습니다.
- i가 n의 약수라면 n/i 역시 n의 약수이므로, 약수는 항상 (i, n/i) 쌍으로 존재합니다.
- 따라서 i와 n/i가 서로 다르면 개수를 2씩 증가시키고, 두 값이 같은 경우(i가 n의 제곱근인 경우)에는 개수를 1만 증가시킵니다.
- 이 방식으로 √n까지만 반복해도 전체 약수의 개수를 정확히 구할 수 있으며, 시간 복잡도는 O(√n)입니다.
전체 구현 코드는 다음과 같습니다.
예제 코드
import math
def countDivisors(n):
count = 0
# 1부터 √n까지 반복하며 모든 약수를 계산
root = int(math.sqrt(n)) + 2
for i in range(1, root):
if (n % i == 0):
# 나눈 몫과 나누는 수가 같으면(제곱근인 경우) 1을 더하고,
# 그렇지 않으면 약수가 쌍으로 존재하므로 2를 더함
if (n // i == i):
count = count + 1
else:
count = count + 2
if (count % 2 == 0):
print("Even")
else:
print("Odd")
# 위 함수를 테스트하는 드라이버 코드
print("The count of divisor: ")
countDivisors(100)
출력 결과
The count of divisor: Odd
100의 약수는 1, 2, 4, 5, 10, 20, 25, 50, 100으로 총 9개이며, 이는 홀수이므로 "Odd"가 출력됩니다.
참고: 완전제곱수의 특성
수학적으로 흥미로운 사실은, 어떤 수의 약수 개수가 홀수가 되려면 그 수가 반드시 완전제곱수여야 한다는 점입니다. 일반적인 수는 약수가 (i, n/i) 형태의 쌍으로 존재하지만, 완전제곱수의 경우 제곱근에서만 쌍을 이루지 못하고 단독으로 존재하기 때문입니다. 따라서 n이 완전제곱수인지만 확인하면 O(1) 시간에도 답을 구할 수 있습니다.
결론
이 글에서는 주어진 숫자의 약수 개수가 짝수인지 홀수인지 확인하는 방법에 대해 알아보았습니다. √n까지만 반복하여 약수를 세는 방식은 O(√n)의 시간 복잡도를 가지며, 완전제곱수 여부를 확인하는 수학적 성질을 활용하면 더욱 효율적으로 문제를 해결할 수 있습니다.