어떤 수로도 나누어 떨어지는 가장 작은 수 c++

설명

http://euler.synap.co.kr/ 5번 문제입니다.

문제

1 ~ 10 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 2520입니다.
그러면 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 얼마입니까?

코드

파이썬 2.7  

Project euler

[Project euler]5. 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수

문제)

1 ~ 10 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 2520입니다.

그러면 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 얼마입니까?

과정)

먼저 프로그래밍으로 코딩해 보았다.

단순한 반복문으로 쉽게 작성할 수 있었다.

이제, 수학적으로 증명해볼 시간이다.

1번문제를 제외하고는 수학적 접근이 어려웠는데

이번 문제는 왠지 가능할 것 같았다.

어쩌면 최소공배수를 구하는 문제같은 느낌을 받았기 때문이다.

우선 1 ~ 10 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 2520이였다.

1은 모든 자연수로도 나누어 떨어지므로 사실상 2 ~ 10 사이로 계산할 수 있을 것이다.

(다시보니 위 반복문도 1번 줄일 수 있을 듯...)

2) 2 3 4 5 6 7 8 9 10

2) 1 3 2 5 3 7 4 9 5

2) 1 3 1 5 3 7 2 9 5

3) 1 3 1 5 3 7 1 9 5

3) 1 1 1 5 1 7 1 3 5

5) 1 1 1 5 1 7 1 1 5

7) 1 1 1 1 1 7 1 1 1

1) 1 1 1 1 1 1 1 1 1

즉, 다수의 최소공배수를 구하는 공식으로 수학적으로 접근이 가능했다.

그렇다면 위의 코딩도 조금은 변할 수 있을 것이다.

위 코드는 1 ~ max 사이의 최소공배수를 구하는 코드이다.

굳이 1은 필요없으므로 제외한다면 1일때 반복하는 횟수를 줄일 수 있을것이다.

최종 결과값인 num이 2520이며 max에 20을 대입하여 정답을 구할 수 있을 것이다.

풀이)

1 ~ 20 까지의 최소공배수가 답.

로그)

두 수의 최소공배수를 구하는 공식을 많이 찾을 수 있었는데

gcd(a, b)가 a, b의 최대공약수를 구하는 함수일 때,

lcm(a, b) = gcd(a, b)*a*b; 이다.

초등학교때 배운것들은 까먹더라도 몸에 익히도록 하자.