문제 설명

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

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

제한 조건
n은 2이상 1000000이하의 자연수입니다.

입출력 예
n result
10 4
5 3

효율성 테스트 실패

예전에 풀었던 백준 1978번 소수 찾기 풀이를 참조하여 풀었는데

function solution (n) {
  let count = 0
  for(let i=2; i<=n; i++){
      if(i <= 3){
          count++
      }else{
          const end = parseInt(Math.sqrt(i))
          for(let j=2; j<=end; j++){
              if(i % j === 0){
                  break;
              }else if(j > end-1){
                  count++
              }
          }
      }
  }  
  return count
}

효율성 테스트 4제 중 1,2,4에서 시간 초과가 발생했다..
소수 i를 구하기 위해 i를 나눌 j의 범위를 i의 제곱근 이하로 정한 것은 좋았으나 j가 소수인지 따지지 않고 무조건 +1 증가시킨 것이 주 원인이라고 생각된다.

시간이 오래 걸려 다른 풀이를 바탕으로 학습하기로 했다.

solution

function solution(n) {
    const s = new Set();
    for(let i=1; i<=n; i+=2){
        s.add(i);
    }
    s.delete(1);
    s.add(2);
    for(let j=3; j<n; j++){
        if(s.has(j)){		// j가 소수라면
             for(let k=j*2; k<=n; k+=j){	// j를 제외한 j의 배수를     
                s.delete(k);				// 모두 삭제한다
             }
        }
    }
    return s.size;
}

• 메서드 add, delete, has, size 를 가진 Set을 이용한 풀이.

에라토스테네스의 체
1. 2 ~ n이하의 소수를 구하고자 하는 구간에서 나열하고
2. 소수인 2를 제외한 2의 배수를 모두 지운다.
3. 소수인 3을 제외한 3의 배수를 모두 지운다.
4. 소수인 5을 제외한 5의 배수를 모두 지운다.
...
위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

solution2❓

function solution(n){
  let s = [...Array(n).keys()]
  for(let i=2; i<=parseInt(n**.5)+1; i++){
    for (let j=2; j<=(n-i)/i+1; j++){
      s[i*j-1] = 0
    }
  }
  return s.filter(x=>Boolean(x)).length;
}

n이 9라면
s는 [0, 1, 2, 3, 4, 5, 6, 7, 8] 인데
i의 범위를 2 ~ (n의 제곱근 + 1) 이하로 정하고
j의 범위를 2 ~ ((n-i)/i + 1) 이하로 정하고?
순회하여 s[i*j - 1] = 0 하고??

-> s = [ 0, 1, 2, 0, 4, 0, 6, 0, 0,]
x가 0이면 filter로 제외하고 나머지의 길이를 반환한다?

이게 뭘까...