ECMAScript6로 만든 에라토스테네스의 체

에라토스테네스의 Sieve of Eratosthenes

일정한 범위 내의 숫자 중 소수를 찾는 알고리즘. 재귀를 이용해 짧고 간결하게 구현할 수 있다.

참고로 ECMA6에는 꼬리재귀 최적화(Tail call optimiztion)가 스펙으로 잡혀있다.

const sieve = (numbers, primeNumbers) => {
  primeNumbers = primeNumbers ? primeNumbers : []; // primeNumbers가 없다면 빈 배열을 생성
  if (!numbers.length) return primeNumbers; // 검사를 위한 숫자가 없다면 결과 리턴
  const value = numbers[0];
  return sieve(numbers.filter(i => i % value), primeNumbers.concat([value]));
};

const numbers = [...Array(119).keys()].map(i => i + 2); // 2부터 120까지의 수가 포함된 배열
console.log( sieve(numbers) ); //  [2, 3, 5, ... 109, 113]

파라미터로 입력받은 배열에 변화를 주지 않기 위해 shift(), push() 함수를 사용하지 않았다.