Algorithm (2) 썸네일형 리스트형 에라토스테네스의 체 ‣ 에라토스테네스의 체(Eratosthenes' sieve)고대 그리스의 수학자 에라토스테네스가 고안한 소수를 찾는 알고리즘아래의 사진처럼 마치 체를 치듯이 수를 걸러내어 소수만 남기기 때문에, 에라토스테네스의 체 라고 부른다. ‣ 동작 방식에라토스테네스의 체는 임의의 정수 n이 있으면 그 이하의 소수들을 O(nloglogn)O(nloglogn)O(nloglogn)의 시간 복잡도로 전부 찾아낼 수 있는 상당히 효율적인 알고리즘이다. 에라토스테네스의 체는 다음과 같은 원리로 진행된다.각 수에 대해 그 수의 배수를 모두 제거하는 작업을 수행한다.2의 배수를 제거할 때 n2 \frac{n}{2}2n 번, 3의 배수를 제거할 때 n3 \frac{n}{3}3n 번, 4의 배수를 제거할 때 n4 \frac.. 유클리드 호제법(Euclidean algorithm) ‣ 유클리드 호제법 유클리드에 의해 기원전 300년경에 발견된 가장 오래된 알고리즘으로, 두 수의 최대공약수를 구하는 알고리즘이다. 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 것으로, 서로 호(互)와 덜(나누기) 제(除)를 써서 호제법이다. ‣ 예시: 1071과 1029의 최대공약수 계산하기 [일반적인 방법] 일반적으로 최대공약수를 구한다고 생각한다면, 먼저 소인수분해를 떠올린다. 1071 = 17 x 7 x 3 x 3 1029 = 7 x 7 x 7 x 3 두 수를 소인수분해한 결과, 공통된 소수를 찾으면 된다. 이를 통해 두 수의 최대공약수(GCD)가 " 7 x 3 = 21 "인 것을 알 수 있다. 하지만, 이 방법은 수가 커질 수록, 소인수분해를 수행하기 어려워진다는 단점이 있다. 유.. 이전 1 다음
