주어진 범위에서 약수의 개수가 홀수인 요소 개수 구하기 – 파이썬 프로그램

이 글에서는 주어진 범위 안에서 약수의 개수가 홀수인 요소가 몇 개 있는지 구하는 방법을 알아보겠습니다.

문제 정의

두 수 n과 m으로 이루어진 범위가 주어졌을 때, 해당 범위 내에서 약수의 개수가 홀수인 숫자가 총 몇 개인지 구하는 것이 목표입니다.

접근 방법

수학적으로 잘 알려진 사실 중 하나는 완전제곱수만이 약수의 개수가 홀수라는 점입니다. 일반적인 수는 약수가 쌍을 이루기 때문에 약수의 개수가 항상 짝수이지만, 완전제곱수는 제곱근 자신이 추가적인 약수가 되어 홀수 개의 약수를 가지게 됩니다.

따라서 이 문제는 범위 [n, m] 안에 포함된 완전제곱수의 개수를 세는 문제로 바꿀 수 있으며, 다음 공식으로 간단히 계산할 수 있습니다.

count = ⌊√m⌋ − ⌊√(n−1)⌋

n과 m이 모두 범위에 포함되므로(inclusive), n이 완전제곱수인 경우 발생할 수 있는 오류를 피하기 위해 공식에는 n−1을 사용합니다. 예를 들어 n=25일 때 25 자체도 개수에 포함되어야 하는데, √(n−1)=√24≈4.89 → 4가 되므로 25(√25=5)가 올바르게 계산에 포함됩니다.

구현 예제

# 카운트 함수
def count(n, m):
    return int(m**0.5) - int((n-1)**0.5)

# 메인
n = 25
m = 400
print("Number of odd squares are: ", count(n, m))

출력 결과

Number of odd squares are: 16

코드 설명

count 함수는 m의 제곱근의 정수 부분에서 (n−1)의 제곱근의 정수 부분을 뺌으로써 범위 내 완전제곱수의 개수를 반환합니다. 위 예제에서는 25부터 400 사이의 완전제곱수, 즉 약수가 홀수 개인 수가 총 16개(5²부터 20²까지) 있음을 확인할 수 있습니다. 모든 변수와 함수는 전역 스코프(global scope)에 선언되어 어디서든 접근 가능합니다.

결론

이 글에서는 완전제곱수의 성질을 활용하여 주어진 범위 내에서 약수의 개수가 홀수인 요소의 개수를 효율적으로 구하는 방법을 배웠습니다. 반복문 없이 단순한 제곱근 연산만으로 해결되므로 O(1) 시간 복잡도로 매우 빠르게 동작한다는 점이 이 접근법의 가장 큰 장점입니다.