파이썬_실전 프로젝트

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

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

 

Smallest multiple

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?

 

 

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

두수 A,B의 최대공약수를 G라 하면, A = Ga, B=Gb 이고,

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

 

문제에서 예로 든 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

 

Code

루프문 작성
def getGCD(num1,num2):
    return 1

lcm=1
i=1
while i <= 15:
    gcd = getGCD(lcm,i)
    lcm = lcm*i/gcd
    print(i,gcd,lcm)
    i+=1
1 1 1.0
2 1 2.0
3 1 6.0
4 1 24.0
5 1 120.0
6 1 720.0
7 1 5040.0
8 1 40320.0
9 1 362880.0
10 1 3628800.0
11 1 39916800.0
12 1 479001600.0
13 1 6227020800.0
14 1 87178291200.0
15 1 1307674368000.0

 

최대공약수 계산
def getGCD(num1,num2):
    i=1
    while i <= num2:
        if num1%i==0 and num2%i==0:
            gcd=i
        i+=1
    return gcd

lcm=1
i=1
while i <= 20:
    gcd = getGCD(lcm,i)
    lcm = lcm*i/gcd
    print(i,gcd,lcm)
    i+=1
1 1 1.0
2 1 2.0
3 1 6.0
4 2 12.0
5 1 60.0
6 6 60.0
7 1 420.0
8 4 840.0
9 3 2520.0
10 10 2520.0
11 1 27720.0
12 12 27720.0
13 1 360360.0
14 14 360360.0
15 15 360360.0
16 8 720720.0
17 1 12252240.0
18 18 12252240.0
19 1 232792560.0
20 20 232792560.0

 

 

댓글

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