📌 문제의 조건

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

제한사항 🤔

• n은 2이상 1000000이하의 자연수입니다.

📌 풀이

첫 풀이 👨‍💻

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

  return count
}

더 생각한 후 풀이 👨‍💻

function solution(n) {
  let arr = [];
  for(let i = 2; i<=n; i++){
    arr[i] = i
  }

  for(let i = 2; i <= n; i++){
    if(arr[i] === 0){
      continue;
    }
    for(let j = i+i; j <= n; j+=i){
      arr[j] = 0;
    }
  }

  arr.splice(0,2);
  
  return arr.reduce((acc, cur)=>{
    if(cur !== 0){
      return acc+1
    } else {
      return acc
    }
  }, 0)
}

📌 리뷰

처음엔 제곱근만 이용했다.
그런데 효율성 통과가 안되는 것,
30분동안 눈싸움하다가 모르겠다 싶어서 구글링해보니 에라토스테네스의 체라는 개념이 있어서 적용해보니 풀렸다.
요는 어떠한 숫자의 배수는 소수가 아니니 제외를 해버리고 남은 것들을 세서 반환하는 것이다.
작성하면서도 반복문이 겹친게 두개, 안겹친게 두개나 쓰여서 이게 효율적일지 의문이 들었지만..
결과적으로는 잘 풀렸다.

📌 문제 출처

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges#