[JS] 프로그래머스 / 코딩테스트 입문 / 소수 찾기

---

문제

프로그래머스

---

메모

에라토스테네스의 체

---

정답

// 에라토스테네스의 체

function solution(n) {
  let answer = 0;
  const arr = new Array(n + 1).fill(true);

  for (let i = 2; i <= n; ++i) {
    // 이미 소수가 아닌 인덱스는 건너뛴다.
    if (arr[i] === false) {
      continue;
    }
    // 배수는 소수가 아니라 0으로 설정
    for (let k = i * 2; k <= n; k += i) {
      arr[k] = false;
    }
  }
  // 소수의 갯수를 구한다.
  for (let i = 2; i <= n; ++i) {
    if (arr[i] === true) {
      answer++;
    }
  }
  return answer;
}

// fill 이용해 약수 구하는 방법 - 효율성 실패

function solution(n) {
  let answer = 0;

  for (let i = 2; i <= n; i++) {
    let measures = Array(i)
      .fill(1)
      .map((a, b) => a + b)
      .filter(x => i % x === 0);
    if (measures.length === 2) answer++;
  }

  return answer;
}

---