[알고리즘] 수학 - 정수론 / 약수, 최대공약수와 최소공배수, 소수 ( 유클리드 호제법, 에라토스테네스의 체)

 

 

알고리즘 공부를 시작하기 앞서 기본적으로 먼저 다뤄야 할 수학 부분에서는 대표유형으로 크게 나누면 약수, 소수, 최대공약수와 최소 공배수 유형으로 나누어 볼 수 있다. 각 유형별로 알아야 할 포인트를 다뤄보도록 하겠다.

 

 

 

약수

 

약수를 구하는 방법은 어떤 자연수N이 존재하는 경우 N이하의 자연수로 N을 나누었을 때 나머지가 0이면, 해당 N이하의 자연수는 자연수N의 약수이다. 어떤 자연수 N이 37일 때 코드로 작성하면 다음과 같다.

n=36
for i in range(1,n+1):
    if n%i==0:print(i,end=" ")

결과:

1 2 3 4 6 9 12 18 36

 

하지만 이와 같이 작성하면 시간 복잡도는 O(n)으로 자연수 N이 10^8이 되는 경우 1초의 시간이 걸리게 된다. 

더 적은 시간이 걸리도록 작성할 수 없을까?

 

 

 

 

Point 1) n/2까지 확인하기

36의 약수는 1, 2, 3, 4 ,6 ,9 ,12, 18, 36으로 구성되어 있다. 6을 기준으로 앞의 수와 뒤의 수를 쌍으로 곱하게 되면 36이 된다. 약수의 중간 전까지만 구하면 뒤에 부분도 구할 수 있는 것이 아닐까? -> n까지 비교하는 것이 아닌 n/2까지 구해보자!

 

n=36
for i in range(1,n//2+1):
    if n%i==0:print(i,end =" ")

 

결과:

1 2 3 4 6 9 12 18

 

결과에서 볼 수 있듯이 36만 제외한 나머지가 출력되는 것을 알 수 있다. 실질적으로 시간 복잡도에서 큰 차이를 내지 않는 것으로 알 수 있다. 이를 바탕으로 "약수 중 6이 중간이니까 절반을 나누는 것이 아니라 √N을 통해 구하면 되겠구나!"의 결론으로 이어진다.

 

 

 

Point 2) √n까지 확인하기 

 

n=36
for i in range(1,int(n**(1/2))+1):
    if n%i==0:print(i,end =" ")

결과:

1 2 3 4 6

이와 같이 정상적으로 6전까지 출력되는 것을 볼 수 있다. 자연수 N의 절반까지 계산하는 방식의 시간 복잡도는 실제로 O(N)인 반면, 제곱근 까지 계산하는 방식은 시간 복잡도가 O( √N)으로 감소하는 것을 볼 수 있다.

 

 

 

√ N 이후의 약수를 구하는 방법은 √ N전의 약수로 N을 나누어 주면된다.

이때 36과 같이 어떠한 수의 제곱인 수는 √ N이 2번 포함될 여지가 있다는 것을 인지한다면, 완벽하게 약수를 구할 수 있다. 전체 약수를 구할 수 있는 최적화된 방법은 아래와 같다.

 

n=36
div=[]
for i in range(1,int(n**(1/2))+1):
    if n%i==0:
        div.append(i)
        if i!=n//i:div.append(n//i)

div.sort()  #순서대로 출력하기 위함
print(*div)

결과:

1 2 3 4 6 9 12 18 36

 

 

 

 

최대공약수와 최소공배수 - 유클리드 호제법

 

 

 

 

12와 18의 최대 공약수 와 최소 공배수를 구하는 방법은 우측과 같이 구하게 된다.

말 그대로 12와 18의 약수 중 가장 큰 약수를 최대공약수, 12와 18의 약수의 고비 중 가장 작은 수를 최소공배수라 한다. 이를 코딩 적으로 구하게 되면 어떻게 구해야 할 까? 12와 18의 약수를 구한 뒤 둘의 공통적인 약수들을 따로 분리한 뒤,  그 약수들을 토대로 최대공약수와 최소공배수를 판단하는 경우 풀이할 수 있다.

하지만 위의 방식대로 하게 되면 간단한 최대 공약수와 최소 공배수를 구하는데에 복잡하며 수행시간이 오래 걸리게 된다.

 

최대공약수와 최소공배수를 효율적으로 구할 수 있는 방법은 없을까? 

 

 

 

Point 1)  유클리드 호제법 ( 최대 공약수를 구하는 방법)

유클리드 호제법은 최대공약수(=GCD)를 매우 효율적으로 구할 수 있는 방법을 제시한다.

 

유클리드 호제법

 

 

유클리드 호제법에서 (a,b)의 공약수를 구할  때 예시는  a=18, b=12인 경우 18과 12의 최대 공약수는 12와 6의 최대 공약수와 동일하다는 것을 알려준다. 이후 12를 6으로 나눈 나머지가 0이므로 6이 18과 12의 최대 공약수가 되게 된다.

즉 (a, b)=(b,a%b) 를 반복적으로 시행하여 나머지가 0이 나오는 경우 b자리 해당 자연수가 최대 공약수라는 뜻이다.

 

 

 

 

유클리드 호제법을 구현하는 방식에는 재귀와 반복문 2가지 종류가 있으며 이를 파이썬 코드로 구현하면 다음과 같다.

 

1- while 반복

def gcd(m,n):
    while n != 0:
       t = m%n
       (m,n) = (n,t)
    return abs(m)

 

2- 재귀 반복

def gcd(m,n):
	if m < n:
		m, n = n, m
	if n == 0:
		return m
    if m % n == 0:
		return n
	else:
		return gcd(n, m%n)

 

 

 

 

Point 2) 최소 공배수를 구하는 방법

 

위에서 gcd(최대공약수)를 구한 이후 최소 공배수를 구하는 방법은 매우 간단하다. 

a와 b의 gcd(최대 공약수)가 c라 할 때 최소공배수는 c*(a/c)*(b/c)=a*b/c 와 같다.

 

 

파이썬 코드로 구현하면 코드는 다음과 같다.

def gcd(m,n):
    while n != 0:
       t = m%n
       (m,n) = (n,t)
    return abs(m)

a,b=18,12
print(f"최대공약수 : {gcd(a,b)}")
print(f"최소공배수 : {a*b//gcd(a,b)}")

결과:

최대공약수 : 6
최소공배수 : 36

 

 

 

 

 

소수 - 에라토스테네스의 체

 

소수란? 1과 자기자신을 제외한 약수를 가지지 않는 수를 의미한다.

어떤 자연수 N이 소수인지 아닌지 판별하는 경우 N보다작은 자연수로 나누어지는 경우 소수가 아니다. 나누어지는 수가 없는 경우 자연수 N은 소수이다. 기본적으로 소수를 판별하는 파이썬 코드는 다음과 같다.

 

def decimal(n):
    for i in range(2,n):
        if n%i==0:
            print("소수가 아닙니다.")
            return
    print("소수입니다.")

 

여기에서 소수인지 아닌지 확인 하는 경우도 약수에서와 같이 여러 가지 방법을 활용하여 확인할 수 있다.

위와 같이 어떤 수가 자연수 N인지 확인하는 경우는 매우간단하게 해결이 가능하지만, 예를 들어 1부터 100000까지 사이에 소수를 모두 구하라고 하는 경우 decimal함수를 100000번 호출하여 소수인지 아닌지 확인해야 한다는 문제점이 발생한다. 해결할 수 있는 방법은 없을까?

 

 

 

 

Point 1)  에라토스테네스의 체

 

어떠한 큰 범위에 소수를 파악하기 위해서는 범위 내 모든 자연수 N을 소수인지 아닌지 파악하는 것보다 효율적인 방법이 필요하다. 

소수는 말 그대로 1과 자기 자신을 제외한 약수를 가지지 않는 수를 의미하기 때문에 1을 제외한 어떤 수의 배수인 경우 해당 수는 소수가 아니다. 

 

에라토스테네스의 체는 X의 배수를 지우는 것을 반복하여 소수가 아닌 것을 제외하는 알고리즘이다.

 

예를 들어 1부터 120 사이에 소수를 구하고 싶은 경우 2, 3, 5 ,7... 의 배수를 지우고 난 이후에는 나머지는 소수만 남은 것을 알 수 있다. 

 

왜 2, 3, 5, 7 순으로 소수의 배수만 곱셈으로 지우는가?

-> 2의 배수 3의 배수를 지운 이후 다음 수는 5로 소수이다. 즉 X의 배수를 지우는 경우에도 X의 선택은 소수이게 되는 것을 알 수 있다.

 

X의 범위는 어디까지 하여야 해당 범위의 소수를 다 거를 수 있을까? 

-> 약수에서 활용 방식과 같이 1부터 100까지의 소수를 찾아야 하는 경우 100의 배수까지 다 지우는 경우도 소수를 찾을 수 있지만, 실제로 √ 100의 배수까지 지워도 충분하다. 즉 1부터 N까지 사이에 소수를 찾아야하는 경우   int(√ N)+1의 배수까지만 확인하면 된다.

 

 

 

파이썬 코드로 구현하면 코드는 다음과 같다.

def prime_list(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * n

    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우
            for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False

    # 소수 목록 산출
    return [i for i in range(2, n) if sieve[i] == True]

 

결과:

prime_list(20)
[2, 3, 5, 7, 11, 13, 17, 19]

max(prime_list(1000000))
99998

 

 

 

 

 

 

 

 

 

출처 : 위키백과 https://ko.wikipedia.org/wiki/