소수 (Prime Number)

소수 구하기 (에라토스테네스의 체)

소수(Prime Number)는 약수로 1과 자기 자신만을 가지는 정수입니다. 정수론의 기본 정리에 의해 모든 자연수는 단 하나의 소수들의 곱으로 표현됩니다.

소수 구하는 알고리즘

1. 기본적인 접근
   소수는 1과 N만을 약수로 가진다. 그럼 2부터 N-1까지의 수로는 나눠져서는 안된다.

2. 에라토스테네스의 접근
   주어진 자연수 N이 소수이기 위한 필요충분 조건은 N이 N의 제곱근보다 크지 않은 어떤 소수로도 나눠지지 않는다. 수가 수를 나누면 몫이 발생하게 되는데 몫과 나누는 수, 둘 중 하나는 반드시 N의 제곱근 이하이기 때문이다.

즉, 2부터 N의 제곱근 까지 나눠보면 됩니다.
연산 횟수 : 루트(N-2) 번

3. 에라토스테네스의 체
   에라토스테네스의 체는 매우 간단한 아이디어입니다. 위에서 모든 자연수는 소수들의 곱으로 표현이 된다고 했습니다. 제일 작은 소수 2부터 시작합니다. 2부터 N-1까지의 수 중에서 2의 배수를 모두 체로 거르고 남은 숫자들 중에서 3의 배수로 거르고를 반복해서 제곱근N 까지 나눠서 걸러지지 않고 남은 수들이 모두 소수가 됩니다.

주어진 수가 소수인지 아닌지 판별만 할 경우는 2번째 방법을 사용하는 것이 좋습니다.
그러나 다음 문제처럼 주어진 수 까지의 모든 소수를 구하기 위해서는 에라토스테네스의 체를 사용합니다.

다시 한번 간단하게 에라토스테네스의 체를 정리하며 마무리 하겠습니다.

// 소수 판별기
function isPrime(n) {
	// 1이하일 경우엔 소수가 아닙니다.
	if (n <= 1) return false;

	// 2와 3일 경우엔 소수 입니다.
	if (n === 2 || n === 3) return true;

	// 2로 나눴을 때 나머지가 0일 경우엔 소수가 아닙니다.
	// 이 말인 즉슨 짝수는 다 소수가 아닙니다.
	if (n % 2 === 0) return false;

	// 최대 n - 1까지 돌려줍니다.
	let divisor = 3;
	while (n > divisor) {
		// 무엇이라도 0으로 떨어진다면 소수가 아닙니다.
		if (n % divisor === 0) return false;

		// 짝수일 경우를 제외한 홀수일 경우를 판단
		divisor += 2;
	}

	// 모든 조건을 통과했을 경우 소수로 인정받습니다.
	return true;
}