최소 공배수와 최대 공약수,소인수 분해 프로그래밍적 관점

최소 공배수

초등학교 5학년 때 약수(divisor or factor)와 배수(multiple)를 배운 뒤에 최대공약수(greatest common divisor or greatest common factor) 와 함께 배우게 되는 내용. 공배수(common multiple)란, 이름에서 알 수 있듯이 두 수, 혹은 그 이상의 수들의 공통인 배수라는 뜻이다. 최소공배수(least common multiple)는 당연히 공배수 중에서 가장 작은 것. 두 수 �,�a,b의 최소공배수를 기호로 cm(a,b) 혹은 LCM(a,b)로 표기하며,더욱 줄이면[a,b]로 표기하기도 한다.

간혹 최대공배수로 잘못 부르는 경우가 있는데, 최대공배수는 존재하지 않는다. 공배수는 한없이 커지므로, 가장 큰 숫자를 정의할 수 없기 때문. 마찬가지로 최소공약수 또한 어떤 수 집합이든 무조건 1이므로 의미가 없다.

2. 찾는 법

예시로 두 수 10, 12의 공배수를 찾고 싶다고 하자. 먼저 두 수의 배수를 쭉 나열한다.

10: 10, 20, 30, 40, 50, 60, 70, ...
12: 12, 24, 36, 48, 60, 72, ...

여기서 위아랫줄 동시에 나타나는 수가 바로 공배수이다. 최소공배수는 앞서 설명했듯이 공배수 중 가장 작은 것. 이 예시의 경우에는 60이 최소공배수가 된다. 같은 방법으로 세 수 이상의 최소공배수도 구할 수 있다.

하지만 숫자를 나열하는 방법으로 최소공배수를 찾는게 힘들다면? 이 때는 소인수분해를 이용해서 최소공배수를 찾는다. 10과 12를 각각 소인수분해하면,

10=2⋅510=2⋅5
12=22⋅312=22⋅3

이제 중복되는 소인수는 차수가 큰 횟수만큼, 그리고 나머지 소인수를 모두 곱해주면 그 값이 최소공배수이다. 위 예시에서는 2를 두 번,[3] 3을 한 번, 그리고 5를 한 번 곱한 값, 즉 60이 최소공배수가 된다. 특히, 숫자가 서로소이면, 그냥 아무런 생각도 하지않고 두 수를 곱해주기만 하면 그 값이 최소공배수가 됨을 알 수 있다.

위에서 봤듯이 최소공배수는 대수학적으로는 그 성질을 다루기가 매우 까다롭기 때문에 특수함수에 속한다.

최대공약수 gcd⁡gcd를 이용하는 방법도 있다. 최대공약수와 다음과 같은 관계가 성립한다:

lcm(a, b)=gcd(a,b)∣ab∣​

단, 최대공약수도 최소공배수도 모를 경우 순환논법이 될 수 있음을 주의해야 한다.

 

최대 공약수

정수의 성질 중 하나. 초등학교 5학년 때 나오며, 약수(divisor or factor)에 대해서 먼저 배운 뒤, 바로 배우게 될 것이다. 먼저 공약수(common divisor or common factor)란, 이름에서 알 수 있듯이 두 수, 혹은 그 이상의 여러 수의 공통인 약수라는 뜻이다. 최대공약수 (greatest common divisor) 는 당연히 공약수 중 가장 큰 것. 두 수 a,b의 최대공약수를 수학적 기호로 표시하면, gcd(a,b)이며,더욱 줄여서 (a,b)로 표기하기도 한다. 특히,gcd(a,b)=1이면 두 수 a,b는 서로소(relatively prime, coprime)라고 한다. 중1 입학하면 소인수분해랑 연계해서 더 심화된 과정으로 최소공배수랑 같이 또 나온다. 최대공약수ㆍ최소공배수는 약분과 통분, 분모가 다른 분수의 계산, 분수의 곱셈ㆍ나눗셈, 6학년 때 배우는 비의 성질, 비례식의 성질, 중1 정수와 유리수의 혼합계산, 방정식ㆍ부등식의 풀이 등 다방면으로 나온다.

가끔 최소공약수라고 잘못 부르는 경우가 있는데, 최소공약수는 무조건 1이므로 논할 가치도 없다. 반대로 최대공배수도 결국 무한으로 발산하므로 논할 가치 자체가 없다.

2. 찾는 법

예시로 두 수 12, 18의 공약수 및 최대공약수를 찾고 싶다고 하자. 간단하게, 두 수의 약수를 모두 나열한다.

12: 1, 2, 3, 4, 6, 12
18: 1, 2, 3, 6, 9, 18

여기서 위아랫줄 모두 같이 있는 숫자가 공약수가 된다. 즉, 이 경우에는 1, 2, 3, 6이 공약수가 된다. 최대공약수는, 찾은 공약수 중 가장 큰 것, 즉 이 경우에는 6이 최대공약수가 된다. 같은 방법으로 세 수 이상의 최대공약수도 구할 수 있다.

 

 

 

소인수 분해

 

합성수를 소수들의 곱으로 나타내는 것을 말한다.소수를 처음 배우는 중학교부터 자주는 아니더라도 계속 쓰이는 기본적인 수학 도구. 모든 합성수가 소인수분해된 형태를 가지고 있다는 것은 산술의 기본정리로 증명된다

 

https://www.youtube.com/watch?v=wsTEul5kzTs 소인수분해의 직관적 영상

 

배수 판정

정수 N에 대해서,

1. 2의 배수: 일의 자리 숫자가 짝수.
2. 3의 배수: 각 자릿수의 합이 3의 배수.
3. 4의 배수: 맨 뒤 두 자리가 00이거나 4의 배수.
4. 5의 배수: 일의 자리가 0이거나 5인 경우.
5. 6의 배수: N이 2의 배수이면서 3의 배수.
6. 8의 배수: 맨 뒤 세 자리가 000 또는 8의 배수.
7. 9의 배수: 각 자릿수의 합이 9의 배수.
8. 10의 배수: 일의 자리가 무조건 0.
9. 10n의 배수: 가장 끝의 n개의 자리가 모두 0.
10. 7, 11, 13의 배수: 일의 자리부터 세 자리씩 끊은 뒤, 각 부분을 교대로 빼고 더한 값이 7, 11, 13의 배수.
11. 15의 배수: N이 5의 배수이면서 3의 배수.
12. 25의 배수: 맨 뒤 두 자리가 00 또는 25의 배수(25, 50, 75)
13. 12의 배수: N이 3의 배수이면서 4의 배수.
14. 20의 배수: N이 4의 배수이면서 5의 배수.
15. 30의 배수: N이 5의 배수이면서 6의 배수.
16. 48의 배수: N이 3의 배수이면서 16의 배수.
17. 72의 배수: N이 8의 배수이면서 9의 배수.
18. 27, 37의 배수: 일의 자리부터 3자리씩 끊은 뒤 이들을 모두 합한 결과가 27, 37의 배수인 수.

 

 

프로그래밍에서 소인수 분해를 쓸 때

 

프로그래밍으로 소인수를 구할 때는 위와 같은 자질구레한 규칙을 따질 필요 없이, 주어진 숫자 n의 소인수를 구한다고 할 경우 아래와 같은 순서로 진행하면 된다.

 

* 1. i=2로 시작하여 i++ 하면서 n%i == 0 인지 체크한다.
* 2. n%i==0이 성립하는 경우 i를 소인수로 등록한 후 n은 i로 나눈 값을 저장하고 i는 i++ 하지 않고 i부터 다시 시작하도록 한다.
* 3. n이 1이 될 때까지 위 과정을 반복한다.

 

 

어차피 작은 소수에서 n%i == 0이 성립하지 못한다면 그보다 큰 합성수는 n%i == 0가 성립하지 못하므로 n%i == 0이 성립하는 첫번째 i는 소수라는 점을 이용한 알고리즘이다.
이 알고리즘으로 소인수를 구하면 천억이 넘는 숫자도 소인수가 순식간에 구해진다.

간단하게 파이썬으로 코딩 해보면 다음과 같다.

 

# -*- coding: utf-8 -*-
import os
import sys

def find_prime(input_num):
    if input_num <= 2:
        return [input_num,]
    for idx in range(2,input_num):
        if input_num % idx == 0:
            ret_list = []
            val_a    = find_prime(idx)
            val_b    = find_prime(int(input_num/idx))
            ret_list = val_a + val_b
            return ret_list
    return [input_num,]

def main():
    try:
        input_num  = int(sys.argv[1])
    except:
        print("usage: python main.py <number>")
        print(" ex>   python main.py 12345")
        quit()
    prime_list = find_prime(input_num)
    check_num  = 1
    for prime_at in prime_list:
        check_num *= prime_at
    print("[%s] input_num=%d, check_num=%d" % (input_num == check_num, input_num, check_num))
    print("%s" % prime_list)

main()

다만 위의 프로그램은 프로그래밍을 익히는 용도로는 유용할수 있으나, 실제 소인수분해 용으로 쓰기에는 적합하지 않다. 실제로 컴퓨터로 다루는 수는 1000억은 '겨우'라는 소리가 나올만큼 큰 수를 다룰 필요가 있기 때문이다.

가장 쉬운 방법은 다른 프로그램을 이용해서 미리 소수 테이블을 작성해 두고, 이를 활용하는 것이다. 예를 들어 216 보다 작은 소수는 6542개인데, 이를 미리 배열에 저장해 두면, 42억 (=232 ) 보다 작은 수는 겨우 6542번 나누어 보기만 하면 소수인지 판정하거나, 1개 이상의 소인수를 구할 수 있다. 232 보다 작은 소수는 모두 약 2억개(203,280,221 개) 인데, 이를 미리 구해서 적절한 DB 에 저장해 두면 약 1844경 (= 264 = 18,446,744,073,709,551,616) 보다 작은 수의 소인수 분해를 쉽게 할 수 있다.

20자리 정도 되는 이정도 수면 큰 수라고 생각할 수 있지만, RSA 암호화같은 암호학에서 기본 수백자리 수를 다뤄야 한다. RSA 넘버를 보면 가장 작은 것이 100자리 부터 시작하는데, 그마저 250자리 수 까지는 모두 소인수분해되었다. 가장 큰 RSA-2048 은 무려 617자리 수이다. 수의 단위 중 이름이 붙은 최고 단위인 구골이 101자리 수라는 것을 생각해보면, RSA 암호화에서 다루는 수는 사람에게는 어마어마하게 큰 수이다.

 

출처-나무위키