[예제 다운로드]

※주석을 넣는 중 실수로 지워버린 부분을 수정하였습니다. 그리고 100과 10000등 두 수를 곱하여 999999를 넘어가버리는 수는 변수 최대치 때문에 어쩔 수가 없습니다.

---

일단 이 글을 쓰게 된 경위는, 제가 무언가 게임제작툴 강좌를 해야겠으나, 할 것이 없기에 이거라도...



먼저 최대공약수란 무엇이냐?

두 수가 있을 때 둘이 공통으로 가진 약수 중에 가장 큰 것을 말합니다.
예를 들어서 6의 약수는 1, 2, 3, 6이고 4의 약수는 1, 2, 4 입니다. 공통으로 1, 2를 가졌고 가장 큰 것이 2입니다.


그렇다면 최소공배수는?

두 수가 있을 때 둘이 공통으로 가진 배수 중에 가장 작은 것을 말합니다.
예를 들어서 6의 배수는 6, 12, 18, 24... 이고 4의 배수는 4, 8, 12, 16, 20, 24... 입니다. 공통으로 가진 것 중 가장 작은 것이 24입니다.

최대공약수를 구하는 방법은?

중1 과정에서 소인수분해라는 것을 배웁니다만.. 알만툴로 이거 하려다 미치는줄 알았습니다. 그래서 안했습니다[...-_-]

또 다른 방법으로는 유클리드 호제법이라는게 있는데, 이것이 무엇이냐하면 말입니다.
지식in을 참고하면:

"자연수 a, b에 대하여 a를 b로 나누었을 때, a＝bq＋r 을 만족하는 적당한 정수 q, r이 존재한다. 이 때, gcd(a, b) = gcd(b, r) 이다."

라고 나와있습니다.

나누기를 했을 때 피제수＝제수 × 몫 ＋ 나머지 라는 것은 초등학생도 알 수 있는 것이고..
gcd란 것은 아마 Greatest Common Division이 아닌가하는데 아무튼 한글로는 최대공약수입니다.
즉 피제수와 제수의 최대공약수는 제수와 나머지의 최대공약수와 같다라는 말입니다.

그렇다면 이 원리를 어떻게 쓸 수 있느냐?

52와 36의 최대공약수를 구해보겠습니다.

원래 소인수분해를 하면 2 × 2 × 13, 2 × 2 × 3 × 3 이라는 결과가 나와서 최대공약수는 4입니다마는,
이 방법을 이용하면

52, 36
52－36, 36＝16, 36
16, 36－16＝16, 20
16, 20－16＝16, 4
16－4, 4＝12, 4
12－4, 4＝8, 4
8－4, 4＝4, 4
4－4, 4＝0, 4

여기서 둘 중 하나가 0이 되면 남은 다른 하나가 최대공약수가 됩니다. 그래서 최대공약수는 4입니다.

계산법은, 큰수와 작은 수가 있으면 큰수에서 작은 수를 나누고 나머지를 값으로 가집니다. 그리고 그 과정을 반복합니다. 어느 한쪽이 0이 되면 남은 한 수가 최대공약수이고 두 수가 같아지면 둘 다 최대공약수가 됩니다.


최소공배수를 구하는 방법은?

두 수가 있을 때 첫번째 수 × 두번째 수 ÷ 최대공약수

끝입니다.


최대공약수 및 최소공배수는 알만툴에서 어떻게 활용할 수 있겠는가?

알아서 찾아보시길...[-ㅅ-]