[프로그래머스]연습문제 - 소수찾기

문제확인

https://programmers.co.kr/learn/courses/30/lessons/12921

문제풀이

function solution(n) {
  var answer = 0;
  let count = 0;

  if (n === 1 || n === 0) return (answer = 0);
  if (n === 2) return (answer = 1);

  for (let i = 2; i <= n; i++) {
    for (let j = 1; j <= Math.sqrt(i); j++) {
      if (i % j === 0) count++;
    }
    if (count === 1) answer++;
    count = 0;
  }
  return answer;
}

위 코드는 테스트 케이스는 모두 통과하지만 효율성 테스트를 통과하지 못한다. 그래서 에라토스테네스의 체를 사용해야 한다.

function solution(n) {
  var answer = 0;
  let flag = Array(n + 1).fill(1);
  (flag[0] = 0), (flag[1] = 0);

  if (n === 1 || n === 0) return (answer = 0);
  if (n === 2) return (answer = 1);

  for (let i = 2; i * i <= n; i++) {
    //i = n의 제곱근 이하의 수
    if (flag[i]) {
      //다른 수의 배수였다면 0이 되어있을 테니까
      //만약 i = 5인데 flag[i] = 1이라면 5보다 작은 수의 배수가 된적이 없다
      //즉, 5는 소수이다
      for (let j = i * i; j <= n; j += i) {
        //j = 제곱근의 배수
        flag[j] = 0;
      }
    }
  }
  return (answer = flag.reduce((prev, curr) => prev + curr));
}

참고풀이

참고자료

에라토스테네스의 체
https://www.lgsl.kr/sto/stories/60/ALMA2018030003