Algorithms-[Euclidean algorithm & The Sieve of Eratosthenes ]

오늘은 은근 자주 나오는 유클리드 호제법과 에라토스테네스의 체에 대해서 설명해보겠다.

우선 유클리드 호제법은 최대공약수를 구하는 알고리즘이다. 최대공약수를 알면 최소공배수도 쉽게 알 수 있기 때문에 유클리드 호제법은 보통 최대공약수와 최소공배수를 구할 때 모두 쓰인다. 우선 바로 코드부터 보여주자면 

if(b>a) : 
	a,b = b,a
while(b!=0):
  a=a%b
  a,b=b,a
print(a)

우선 입력받은 두 수중에 큰 수를 정해놓고 큰 수를 작은 수로 계속 나누어서, 나누어 떨어질 때까지 반복한다. 나누어 떨어질 때(나머지가 0일 때), 나누는 수가 최대공약수이다. 이 방법은 a,b의 최대공약수는 (a-b),a의 최대공약수와 같다는 성질 때문이다. 이 때 최소공배수는 a*b를 a와 b의 최대공약수로 나눈 것과 같다. + 최대공약수는 gcd, 최송공배수는 lcm이라고 많이 쓴다. 

다음으로 에라토스테네스의 체는 소수를 구할 때쓰는 알고리즘이다. 이것도 코드부터 보겠다.

def prime_list(n):
    sieve = [True] * n
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] != 0:           
            for j in range(i+i, n, i): 
                sieve[j] = 0
    return [i for i in range(2, n) if sieve[i] == True]

이 알고리즘는 이름에서 나오는 것처럼 체 처럼 걸러내는 것이다. 우선 맨처음 주어진 구간까지 1을 채워놓은 리스트를 만든뒤에, for문을 돌면서 예를 들어 2부터 시작하면 2를 제외한 2의 배수들을 모두 지운다. 2를 제외한 2의 배수들은 2라는 약수를 가지고 있기 때문에 소수가 아니기 때문이다. 다음으로 3을 제외한 3의 배수를 지우고, 4는 이미 지워졌고, 5를 제외한 5의 배수를 모두 지우고 이렇게 반복한다. 이 말을 그림으로 표현하자면 아래와 같다.

에라토스테네스의 체

끝~