[소수 알고리즘] 소수의 특성과 에라토스테네스의 체 소수의 특성소수(Prime Number)는 약수로 1과 자기 자신만을 가지는 정수이다. 정수론의 기본 정리에 의해 모든 자연수는 단 하나의 소수들의 곱으로 표현된다. 예를 들면,$$ 91 = 7 * 13 $$$$ 10164 = 7 * 11^2 * 12 $$이를 소인수 분해의 일의성이라고 하는데 이 특징은 최대 공약수를 구하는데 매우 유용하게 사용될 수 있다. 최대 공약수는 두 개 이상의 자연수가 가지는 약수 중 가장 큰 수이다. 약수 또한 자연수 이므로 하나의 소수들의 곱으로 표현된다. 즉 최대 공약수를 구하려는 수들의 공통된 소수들을 모두 곱해 주면 최대 공약수가 되는 것이다.$$ 300 = 2^2 * 3^1 * 5^2, 18 = 2^1 * 3^2 $..