[python/알고리즘] 약수의 개수 구하기 | 시간 복잡도 줄이기

가장 단순한 방법

• 1부터 n까지 다 돌기

n = 100
divisors = []
for i in range(1, n + 1):
    if n % i == 0:
        divisors.append(i)
print(len(divisors))

계산량 조금 줄이기

• n // 2 까지만 계산한 후 n 추가하기

n = 100
divisors = []
for i in range(1, n//2 + 1):
    if n % i == 0:
        divisors.append(i)

print(len(divisors) + 1)

⭐️ 자연수(N) = 약수(A) * 약수(B) 이용하기

• 모든 자연수는 어떤 두 수 A와 B의 곱으로 나타낼 수 있다.
• 따라서 n의 제곱근까지 약수를 구하면 그 약수들의 짝이 되는 약수까지 자동으로 구해진다.

n = 100
div_count = 0

for i in range(1, int(n ** 0.5) + 1): # 1부터 제곱근까지
    if i * i == n: # 제곱수이면 두 짝이 같기 때문에 + 1
        div_count += 1
        continue

    if n % i == 0: # 제곱수가 아니면
        div_count += 2 # i랑 i의 짝꿍까지 + 2
    
print(div_count)

• 다른 버전

n = 100
div_count = 0

for i in range(1, int(n ** 0.5) + 1):
    if n % i == 0: # 약수면 + 1
        div_count += 1
        if i ** 2 != n: # 제곱근이 아니면 + 1 한 번 더
            div_count += 1
    
print(div_count)

관련 문제

프로그래머스 - 기사단원의 무기