에라토스테네스의 체

에라토스테네스의 체

• 에라토스테네스의 체는 소수 찾기 알고리즘이다.
• "소수"란 1과 자신 이외에 자연수로는 나눌 수 없는 자연수이다. ( 2, 5, 7 등)
  1.  1~100까지의 숫자를 나열.
  2.  소수가 아닌 1을 제거.
  3.  2를 제외한 2의 배수를 제거.
  4.  3을 제외한 3의 배수를 제거.
  5.  4의 배수는 2의 배수로 이미 지워졌으므로 5를 제외한 5의 배수를 제거한다.
  6.  6또한 3의 배수로 지워졌으므로 7을 제외한 7의 배수를 제거.
  7.  11 부터는 11^2 > 100 이기에 지울 필요가 없다.
• 이런 알고리즘으로 주어진 n이하의 소수를 찾고 싶을 때 사용할 수 있다.

 

자바스크립트로 구현

function solution(n) {
  //n + 1 개의 요소를 가진 배열 생성 모두 true로 변경 후 소수제외값 0,1 을 false로 변경
  let result = Array(n + 1)
    .fill(true)
    .fill(false, 0, 2);

  // 소수 시작값인 2부터 반복문 시작 i * i 인 이유는 n의 값보다 큰 i 배수까지 반복문을 돌릴 필요는 없기때문.
  for (let i = 2; i * i <= n; i++) {
    //배열이 true면
    if (result[i]) {
      // 중첩 반복문 실행. j에 i를 대입해가며 주어진 i의 배수를 제거
      for (let j = i * i; j <= n; j += i) {
        result[j] = false;
      }
    }
  }

  return result;
}

let resultFn = solution(100);

//filter메소드의 true일 경우만 새로운 배열에 들어가는 점을 이용.
resultFn.filter((v) => v).length;

// 소수 자체를 알고싶다면 map메소드를 이용해서 v가 true일 경우 index값을 넣어주고 false일 경우 0을 넣어준다.
// 이후 filter함수로 배열을 걸러서 새로 생성. (0 == false 를 이용)
resultFn.map((v, i) => (v ? i : 0)).filter((v) => v);

• 프로그래머스 1레벨 소수 찾기 풀 때는 이해 못 했었는데 지금은 확실하게 이해했다👍