파이썬_실전 프로젝트

프로젝트 오일러 5번문제 - 최소공배수

Q-005

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

 

1~20까지 공통의 배수, 최소공배수(LCM)를 구하는 문제입니다.

최소공배수는 최대공약수(GCD)를 먼저 계산하면 쉽게 찾을수 있습니다.

수학적으로 계산하면, 두수 A,B의 최대공약수를 G라 하면, A = Ga, B=Gb 이고,

최소공배수는 Gab(또는 A*B/G) 가 됩니다.

결국은 최대공약수를 먼저 찾아야 되는 문제입니다.

 

1. 일단 기본은 루프문이 되겠네요.

2. 각 루프에서, 두숫자의 최대공약수와, 최소공배수를 계산하고, 다음루프에서 이전 최소공배수와 다음 숫자와의 새로운 최소공배수를 계산하면 될것 같습니다.

예로 든 1~10을 보면,

1~2 : gcd 1, lcm 2  #1과 2의 최대공약수는 1, 최소공배수는 2, 2를 다음루프로 넘겨줍니다.

2~3 : gcd - , lcm 6  #이전루프의 최소공배수 2와, 새로운 수 3과의 최소공배수를 다시 계산하고, 넘겨줍니다.

6~4 : gcd 2, lcm 12 

12~5 : gcd - , lcm 60

60~6 : gcd -, lcm 60

60~7 : gcd - , lcm 420

420~8 : gcd 4 , lcm 840

840~9 : gcd -, lcm 2520

2520~10 : gcd 10 , lcm 2520

 

그럼 먼저 루프문을 만들어 보겠습니다.

   

def get_gcd(num1,num2): #gcd를 계산해주는 함수
    return 1
     
i=1; gcd=0; lcm=1
while i<10:
    gcd=get_gcd(lcm,i+1) #gcd함수 호출 :직전의 최소공배수와 현재 루프의 수를 넘겨줌.
    if gcd==0:
        lcm = lcm*(i+1)  #gcd값이 없을경우에 최소공배수는 그냥 두수의 곱
    else:
        lcm = lcm*(i+1)/gcd  #gcd값이 있을경우 최소공배수는 두수의 곱에 gcd를 한번 나눠준값
    i=i+1

 

일단 루프가 잘 작동하는지 보기 위해서, 함수 리턴값은 그냥 1로 주고, 값을 지켜봅니다.

def get_gcd(lcm,num):
    return 1
     
i=1; gcd=0; lcm=1
while i<10:
    gcd=get_gcd(lcm,i+1)
    if gcd==0:
        lcm = lcm*(i+1)
    else:
        lcm = lcm*(i+1)/gcd
    i=i+1

정상적으로 작동하면 1부터 10까지 그냥 곱한 3628800 이 나옵니다.

 

이제 get_gcd() 함수, gcd를 계산하는 코드를 만들어야겠네요.

gcd는 유클리드 알고리즘이라고 하는 방식이 있긴합니다만, 지금은 그걸 사용하지 않고, 그냥 직관적으로 루프돌면서 계속 나누어봐서, 나머지가 둘다 0이 되는지를 계속 확인하는 방식으로 하겠습니다. 그중에서 가장 큰값이 최대공약수가 되겠죠.

def get_gcd(num1,num2):
    gcd=1
    loop=num1
    if num1>num2:    #작은수를 기준으로 루프돌리기 위해서, 크기비교.
        loop=num2
    i=1
    while i<=loop:    #작은수 기준 루프.
        if num1%i==0 and num2%i==0:  #두수가 동시에 나누어 떨어지면,
            gcd =i      #그때의  i값을 최대공약수로 저장.
        i+=1
    return gcd          #최대공약수값 리턴.

여기까지 해서, 예제에 나온대로 2520 이 나왔으면, 성공한거고,

문제를 풀기위해서는 , 1~10까지의 수를 1~20 으로 바꿔주기만 하면 됩니다.

 

댓글

댓글 본문
작성자
비밀번호
버전 관리
노마드
현재 버전
선택 버전
graphittie 자세히 보기