[lv1] 소수 찾기

문제 링크

• 1부터 입력받은 숫자 n 사이에 존재하는 소수의 개수 반환

  소수 : 2 이상의, 1과 자기 자신으로만 나누어지는 수

function solution(n) {
    let result = 1;
    for (let i = 3; i<=n; i += 2) {
        if(isPrime(i)){
            result += 1;
        }
    }
    return result;
}

function isPrime(x) {
  for (let i = 2; i <= Math.sqrt(x); i++) {
    if (x % i === 0) return false;
  }
  return true;
}

소수를 구하는 함수를 따로 만들어서 실행.
처음 for(let i = 2; i<=2; i++) 조건으로 반복을 돌렸을 때는 정확도는 모두 통과했으나 효율성에서 전부 탈락.
그 다음에 2 이상의 짝수는 어차피 소수가 될 수 없다는 조건으로 위 식을 완성했다. 2는 처음부터 소수로 result에 포함시켜두고 3부터 시작 i를 2씩 증가시켰다.
결과 효율성 테스트 4개 중 3개 통과. 나머지 하나를 통과하는 방법을 도저히 찾을 수 없어 결국 다른 분의 식을 참고했다.
다른 방법은 없는지 찾아보다가 기존 식으로 테스트를 통과하는 코드를 찾았다

통과한 코드

function solution(n) {
    // 1부터 입력받은 숫자 n 사이에 있는 소수의 개수 반환
    // 소수는 2 이상의, 1과 자기 자신으로만 나누어지는 수
    let result = 1;
    for (let i = 3; i<=n; i += 2) {
        if(isPrime(i)){
            result += 1;
        }
    }
    return result;
}

function isPrime(x) {
  // Prime인지 확인하는 식에서도, 짝수로는 나눠볼 필요가 없으므로 홀수만 판단하도록 추가
  for (let i = 3; i <= Math.sqrt(x); i+=2) {
    if (x % i === 0) return false;
  }
  return true;
}

다른 사람의 풀이

function solution(n) {
    const s = new Set();
  // 1부터 홀수를 s에 모두 추가
    for(let i=1; i<=n; i+=2){
        s.add(i);
    }
    s.delete(1);
    s.add(2);
    for(let j=3; j<Math.sqrt(n); j++){
        if(s.has(j)){ // 소수의 배수는 모두 제거
             for(let k=j*2; k<=n; k+=j){    
                s.delete(k);
             }
        }
    }
    return s.size;
}