📝 에라토스테네스의 체란?

• 소수를 찾는 빠르고 쉬운 방법.
  => 고대 그리스 수학자 에라토스테네스가 발견.

📌 알고리즘

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열.
2. 자기 자신을 제외한 2의 배수를 모두 지운다.
3. 남아있는 수 가운데 3은 소수이므로 3을 제외한 3의 배수를 모두 지운다.
4. 남아있는 수 가운데 5는 소수이므로 5를 제외한 5의 배수를 모두 지운다.
   ...
5. 위의 과정을 계속 반복하면 구하는 구간의 모든 소수가 남게된다.

그림의 경우, 11² > 120 이므로 11보다 작은 수의 배수들만 지워도 충분.
즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수.

📝 에라토스테네스의 체를 활용하여 소수 구하기

function findPrimes(n) {

	const primes = [];
  	const sieve = new Array(n + 1).fill(true);
  	sieve[0] = sieve[1] = false;
  
  	// 제곱근까지 확인하는 이유는 n의 제곱근보다 큰 모든 소수의 배수는
	// 이미 n의 제곱근 이하의 소수들에 의해 걸러지기 때문.
  	for (let i=2; i<=Math.sqrt(n); i++) {
		if (sieve[i]) {
          
          	// j를 i * 2 부터가 아닌  i * i 부터 시작하는 이유는 i 보다 작은
          	// 모든 소수에 대해 이미 배수들이 체크되었기 때문.
          	// ex) i가 3일 때 2의 배수들은 이미 걸러졌으므로, 3의 배수 중 강 작은 미처리된 배수
          	// 3 * 3인 9부터 시작.
			for (let j=i*i; j<=n; j+=i) {
				sieve[j] = false;
			}
		}
	}

	for (let i=2; i<=n; i++) {
		if (sieve[i]) {
			primes.push(i);
		}
	}

	return primes;
  
}