[Lv1] 소수찾기

프로그래머스

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

나의 풀이(1)

수도코드

• n은 2이상 1000000이하의 자연수이므로 무조건 하나의 소수(2)를 갖는다.
• 따라서 3부터 n까지의 숫자(i)를 방문한다.
  • i가 2로 나누어떨어진다면 패스 (continue는 i++로 넘어감)
  • i가 3부터 Math.sqrt(i)까지의 숫자(j)로 나누어떨어진다면 cnt를 하나 빼주고 반복문 중지 (cnt를 빼주는 이유는 break이후에 cnt++가 있기 때문)
  • i가 3부터 Math.sqrt(i)까지의 숫자(j)로 나누어떨어지는 숫자가 없다면 cnt++
• cnt 리턴

function solution(n){
  let cnt = 1;
  if(n===2) return cnt;
  for(let i=3; i<=n; i++){
    if(i%2===0) continue; //짝수인 경우는 패스
    for(let j=3; j<=Math.sqrt(i); j++){
      if(i%j===0){
        cnt--;
        break;
      }
    }
    cnt++;
  }
  return cnt;
}

나의 풀이(2)

수도코드

• 첫번째 풀이와는 다르게 변수 isPrime을 활용해 불필요하게 cnt-- 해주는 과정을 생략했다.

function solution(n){
  let cnt = 1;
  let isPrime = true;
  
  for(let i=3; i<=n; i++){
    for(let j=2; j<Math.sqrt(i); j++){
      if(i%j===0){
        isPrime = false;
        break;
      }
    }
    if(isPrime) cnt++;
    isPrime = true;
  }
  return cnt;
}

---

두가지 풀이법 모두 테스트는 모두 통과했지만, 효율성 테스트는 통과하지 못했다.

다른분의 풀이 (1)

• 에라토스테네스의 체 방식을 활용한다. 각 수의 배수에 해당하는 수는 소수가 아니므로 지워나가는 형식이다.

function solution(n){
  let answer = 0;
  let arr = new Array(n+1).fill(true); //인덱스와 값을 맞추기 위해 +1 해줌.
  
  for(let j=2; j<=n; j++){
    if(!arr[j]) continue;
    
    for(let k=j*2; k<=n; k+=j){
      arr[k]=false;
    }
  }
  
  for(let i=2; i<=n; i++){
    if(arr[i]>0) answer++;
  }
  return answer;
}

다른 분의 풀이(2)

• Set를 사용한다.
• i가 1부터 홀수들만 Set에 추가한다. (짝수는 자동으로 거를 수 있다) 단, 1은 삭제하고, 2를 추가해준다.
• n의 제곱근보다 작은 홀수들이 Set에 존재하는지 확인하고, 있다면 그 홀수의 배수들을 삭제한다.
• Set의 크기를 리턴한다.
• 신기한 방법이지만 효율성 테스트에서 걸리는 시간이 배 이상 차이나므로 적합한 풀이는 아닌 것 같다.

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<=Math.sqrt(n); j+=2){
    if(s.has(j)){
      for(let k=j*2; k<=n; k+=j){
        s.delete(k);
      }
    }
  }
  return s.size;
}

---

제곱근의 성질을 이용해 문제를 푸는 경우에는, 어떤 숫자가 소수인지 판별할때 사용했다. A라는 숫자가 소수인지 확인하기 위해서는 3부터 3의 제곱근까지의 숫자로 나누어떨어지는지를 확인하면 된다.

그런데, 이 문제에서는 특정 구간의 숫자에서 소수의 개수를 구해야한다. 예를 들어, 3부터 500까지의 숫자에서 소수의 개수를 구할때, 내가 푼 방법처럼 각각의 숫자에 대해 3부터 제곱근까지를 모두 확인한다면, 효율성 테스트를 통과할 수 없다.

따라서, 에라토스테네스의 체 방식을 사용해 각 숫자의 배수들은 모두 걸러서 검사해야하는 숫자의 개수를 줄여야한다.