[파이썬, Python] 약수 구하기

Python 약수 구하기

파이썬으로 약수를 구하는 함수를 다양하게 정리해보았다.

 

 

기본적인 방법

1부터 입력한 수(n)까지 다 나눠지는지 확인하면서 약수를 구하는 방법이다.

def get_divisor(n):
    data = []

    for i in range(1, n + 1):
        if n % i == 0:
            data.append(i)
    return data


print(get_divisor(8))

 

 

범위를 축소한 버전 1

1부터 입력한 수(n)를 2로 나눈 값까지 다 나눠지는 수인지 확인하면서 약수를 구하는 방법이다.

def get_divisor(n):
    data = []

    for i in range(1, n // 2 + 1):
        if n % i == 0:
            data.append(i)
    data.append(n)
    return data

print(get_divisor(8))

 

 

범위를 축소한 버전 2

1부터 입력한 수(n)의 양의 제곱근까지 다 나눠지는 수인지 확인하면서 약수를 구하는 방법이다.

def get_divisor(n):
    front = []
    back = []

    for i in range(1, int(n ** (1 / 2)) + 1):
        if n % i == 0:
            front.append(i)
            if i != n // i:
                back.append(n // i)
    return front + back[::-1]


print(get_divisor(8))

 

 

범위를 축소한 버전 3

범위를 축소한 버전2에서 front와 back으로 나눠서 합쳤던 것을 set 자료형을 사용해 작성한 버전이다.

def get_divisor(n):
    data = set()

    for i in range(1, int(n ** (1 / 2)) + 1):
        if n % i == 0:
            data.add(i)
            data.add(n // i)
    return sorted(data)


print(get_divisor(8))

 

 

 

 

 

 

 

 

https://inuplace.tistory.com/459

[알고리즘 연습] 약수 구하기 효율화 (by Python)