소수 구하는 알고리즘
소수는 약수로 1과 자기자신만을 가지는 정수이다. 또한, 모든 자연수는 단 하나의 소수들의 곱으로 표현된다.
기본적인 접근은 소수는 1과 N만을 약수로 가진다. 그럼 2부터 N-1까지의 수로는 나눠져서는 안된다.
에라토스테네스의 체
모든 자연수는 소수들의 곱으로 표현이 된다고 했는데, 제일 작은 소수 2부터 시작한다. 2부터 N-1까지의 수 중에서 2의 배수를 모두 체로 거르고 남은 숫자들 중에서 3의 배수를 거르고를 반복해서 제곱근 N까지 나눠서 걸러지지 않고 남은 수들이 모두 소수가 된다.
