약수 구하기

약수 구하기

먼저 전체 소스부터...

def measure(n):
    '''어떤 수 n 에 대한 약수를 구합니다. '''
    measure_ilst = [n]

    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            measure_ilst.append(i)
            measure_ilst.append(n//i)
            

    return sorted(list(set(measure_ilst)))

        
while True:
    try:
        n = int(input("약수를 구할 숫자를 입력해 주세요.: "))
        
        if n > 0:
            break
        else:
            print("양의 정수만 입력 가능합니다.")
    except:
        print("양의 정수만 입력 가능합니다.")

print(measure(n))

가장 기본적인 약수 구하기

위 소스를 이해하려면 차근차근 약수구하기를 진행해야 이해가 간다.

 

어떤 수(여기에서는 10)가 입력되었다고 가정하자.

그러면 이 수를 1부터 나눠가면서 떨어지는 수를 구해야 한다. 나누어 떨어져야지만 약수가 되기 때문이다.

n = 10

for i in range(1, n+1):
    if n % i == 0:
        print(i, end=" ")
        
print()

여기에서 보듯이 1부터 입력된 숫자(10) 까지 반복문을 통해 검증한다.

만약 n 을 1로 나눠 떨어지면 약수이므로 출력하고 다음 숫자 2로 넘어간다.

n을 2로 나눠 떨어지면 역시 약수이므로 출력하고 다음 숫자 3으로 넘어간다.

n을 3으로 나누면 나머지가 생기므로 약수가 아니다.

이런씩으로 10까지 돌면 1, 2, 5, 10의 약수를 찾을 수 있다.

두 번째 방법

위에서 나온 약수를 잘 보면 5 이후에는 약수가 생기지 않는다. 이 5는 10의 절반이다.

어떤 수 n의 절반 (n / 2) 이상 에서는 n의 약수가 존재하지 않는다. 수학적 증명은 하지 못하므로 패스😊

이를 이용해 알고리즘을 개선할 수 있다.

n = 10

for i in range(1, n//2 + 1):
    if n % i == 0:
        print(i, end=" ")
        
print(n)

n을 2로 나눠 절반의 수를 구한다. (위에서 설명한 대로 절반 이상에서는 약수가 존재하지 못하기 때문)

나머지는 기본적인 구조와 같다.

대신 원래의 수 n도 약수가 되어야 하므로 제일 마지막에 print(n)으로 출력해 준다.

세 번째 방법

이건 수학이 약해 설명하기가 어렵다.😥

제곱과 제곱근을 이용한 공식인데 그냥 외웠다.

어떤 수 n(여기서는 30)이 있다고 가정하자.

30의 약수는 1, 2, 3, 5, 6, 10, 15, 30 이다.

이는 1 x 30, 2 x 15, 3 x 10, 5 x 6 과 6 x 5, 10 x 3, 15 x 2, 30 x 1 이 된다.

즉 앞의 4개와 뒤의 4개는 역순 관계다. 따라서 앞의 4개만 찾으면 뒤의 4개는 자동으로 따라오게 마련다.

그리고 앞의 4개 중 가장 마지막 숫자 5는 30의 제곱근(5.477...) 과 비슷하다.

따라서 30의 제곱근 까지 구한 수에서만 약수를 구하고, 나눈 몫을 구해주면 해결된다.

n = 30

for i in range(1, int(n**0.5) + 1):
    if n % i == 0:
        print(i, end=" ")
        print(n//i, end=" ")

하지만 여기서 하나 더 짚고 넘어가야 할 부분이 있다면 n이 25 처럼 5 x 5 즉 약수의 제곱이 되는 경우에는 5가 2번 찍히게 된다. 따라서 아래 처럼 코드를 변경해야 한다.

n = 25

for i in range(1, int(n**0.5)):
    if n % i == 0:
        print(i, end=" ")
        print(n//i, end=" ")

i += 1        
if i**2 == n:
    print(i)

정리

이제 처음의 알고리즘으로 돌아가서 다시 보자.

def measure(n):
    '''어떤 수 n 에 대한 약수를 구합니다. '''
    measure_ilst = [n]

    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            measure_ilst.append(i)
            measure_ilst.append(n//i)
            

    return sorted(list(set(measure_ilst)))

        
while True:
    try:
        n = int(input("약수를 구할 숫자를 입력해 주세요.: "))
        
        if n > 0:
            break
        else:
            print("양의 정수만 입력 가능합니다.")
    except:
        print("양의 정수만 입력 가능합니다.")

print(measure(n))

함수 measure(n) 에 어떤 수 n이 들어올 경우 약수를 저장할 리스트를 생성한 다음 원래 수 n을 넣어둔다.

그리고 약수 구하는 알고리즘 세 번째 방법의 앞 방법으로 약수를 모두 구해준다. 25의 약수처럼 5 x 5가 되어도 일단 리스트에 입력해둔다.

그 입력된 리스트를 set 키워드를 이용해 집합 자료형으로 바꿔준다. (집합 자료형은 중복된 원소가 있을 경우 하나만 남기고 삭제? 통합? 해 버린다. 즉 중복을 허용하지 않는다.)

그렇게 중복이 제거된 집합 자료형을 다시 리스트로 바꿔준 후 정렬해 주면 모든 약수가 구해짐을 알 수 있다.

 

이렇게 약수 구하는 방법을 공부해 봤는데, 아주 쉬운 내용이지만 쉽지가 않다.

모든 알고리즘을 최적화 하기란 엄청난 공부가 필요함을 다시금 느끼게 된다.

하루에 1개의 알고리즘을 풀어보자고 했지만, 어떤 건 하루 종일 생각해야 하는 알고리즘도 있고, 보자말자 떠오르는 알고리즘도 있더라.

 

그냥 꾸준하게 하는것 만이 답이라 생각해야겠다.

관련 글

2021/01/25 - [프로그래밍/알고리즘] - 소수 구하기