S E P H ' S

에라토스테네스의 체는 가장 대표적인 소수(Prime Number) 판별 알고리즘이다. 임의의 자연수 n에 대해 그 이하의 모든 소수를 찾는 가장 간단하고 빠른 방법이다. 먼저 입력받은 수가 소수인지 판별하는 알고리즘을 작성해보자. def prime(n): for i in range(2, n): if n % i == 0: return False return True 위와 같은 알고리즘의 시간복잡도는 O(N)이다. 주어진 모든 경우의 수 만큼 반복문을 돌며 약수 여부를 확인하기 때문에 매우 비효율적이다. 예를 들어 숫자 8의 경우 2 * 4 = 4 * 2와 같은 식으로 대칭을 이루기 때문이다. 더 간단하게 생각해보더라도 반복문에서 n이 8이라고 가정한다면 2에서 이미 한번 False가 반환되지만 반복이 계속..

유클리드 호제법은 두 수의 최대공약수를 구하는 알고리즘이다. 일반적으로 최대공약수를 구하려면 소인수분해를 해야한다. 1112 = 139 X 2 X 2 X 2 695 = 139 X 5 두 수를 소인수분해한 후, 공통된 소수를 찾으면 된다. 이를 통해 두 수의 최대공약수는 139라는 것을 알 수 있다. 하지만 소인수분해로 최대공약수를 구하는 방법은 수가 커질 수록 어려워진다는 단점이 있다. 나머지 연산인 MOD 연산을 사용한 유클리드 호제법을 사용하면 쉽게 최대공약수를 구할 수 있다. x,y 두 수가 있을 때, x,y의 최대공약수는 y,r의 최대공약수와 같다는 원리를 사용한다. 즉, x에는 y를 y에는 x%y를 대입하여 0이 되는 순간 y의 값이 최대공약수인 것이다. x % y = r 일때, GCD(x,y)..