문제 설명

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

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

제한사항

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

입출력 예

문제풀이

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

    for (let i = 0; i < innerEa.length; i++) {
      for (let j = 2; j < innerEa[i]; j++) {
        //     console.log(innerEa[i])
        if (innerEa[i] % j === 0) {
          innerEa.splice(innerEa.indexOf(innerEa[i]), 1, 0);
        }
      }
    }
    //console.log(innerEa);
    return innerEa.filter((n) => {
      return n !== 0;
    }).length;
  }

풀이에 실패했다. 나중에 다시 도전할 때 어떤 로직으로 시도했는지 기억해두려고 적어둔다.

테스트 케이스 12개중 3개가 시간초과로 실패한다. 아마 n 이 매우 큰 경우 실패하는 것 같다.

for 문이 너무 많은가 싶어 하나를 줄이고 했는데도 실패했다.

function solution(n) {
  let innerEa = [];
  for (let i = 2; i <= n; i++) {
    innerEa.push(i);
    for (let j = 2; j < i; j++) {
      if (i % j === 0) {
        innerEa.splice(innerEa.indexOf(innerEa[i]), 1, 0);
      }
    }
  }
  //console.log(innerEa);
  return innerEa.filter((n) => {
    return n !== 0;
  }).length;
}

생각나는데로 최대한 줄여봤는데 여전히 3개가 시간초과로 실패한다.

반복문을 돌며 n 사이의 개수를 innerEa 안에 넣었고, 그 안의 값을 돌며 소수를 찾아 소수인 경우 0 으로 변경해 리턴할 때 0이 아닌 것들의 개수를 찾았는데 시간초과가 걸린다. 계속 생각해봐야 할 것 같다.

위의 구문에 innerEa[i] 가 0 인 경우도 반복문에서 다음으로 진행하도록 추가해 해봤는데 시간은 조금 줄었지만 3개의 케이스는 여전히 실패한다.