개요 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법. 이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다. 방법 소수를 찾는 가장 간단한 방법이자 가장 무식한 방법이다. 1~50까지의 소수를 찾는 방법을 예를들면, 일단 1부터 50까지 숫자를 쭉 쓴다. 일단 1을 지우자.(1은 소수도, 합성수도 아니며, 기초수라고 해서 별도로 분류한다) 2를 제외한 2의 배수를 지우자 (2는 유일한 짝수 소수이다) 3을 제외한 3의 배수를 지우자 4의 배수는 지울 필요없다(2의 배수에서 이미 지워졌다) 2,3 다음으로 남아있는 가낭 작은 수, 즉 5의 배수를 5를 제외하고 지우자 참고자료 참조 https://namu.wiki/w/%EC%97%90%EB%9..

알고리즘 문제해결 전략 1권에서 설명한 내용은 이렇다. 유클리드 알고리즘은 두 수 p,q(p>q)의 공약수의 집합은 p-q와 q의 공약수 집합과 같다는 점을 이용한다. 증명 a,b의 공약수 g가 있다고 할때, a=ag, b=bg 로 쓸 수 있다. 그러면 a-b=(a-b)g 이므로 g는 a-b와 b의 공약수이기도 하다. 반대 방향도 같은 방법으로 보일 수 있다. 따라서 a,b의 최대공약수 gcd(a,b)는 항상 a-b와 b의 최대공약수 gcd(a-b,b)와 같다. 이 성질을 이용해 6과 15의 최대공약수를 구해보면.. gcd(6,15) = gcd(9,6) = gcd(3,6) = gcd(3,3) = gcd(0,3) 이 과정을 반복하면 이와 같이 결과적으로 어느 한 수가 0이 된다. 0과 3의 최대공약수는 3..