[프로그래머스 lev1/JS] 소수 찾기

문제 출처

프로그래머스 lev1 - 소수 찾기

문제

나의 풀이

1차 시도 (시간초과)

function solution(n) {
  
  // 시간초과 
  let sum=0; 
  let answer = [];
  for (let i=1; i<=n; i++) {
    for (let j=1; j<=i; j++) {
      if (sum>i+1) break;
      if (i%j===0) {
        sum+=j; 
      }
    }

    if (sum===i+1) {
      answer.push(i);
    }
    sum=0; 
  }
  return answer.length; 
}

console.log(solution(10));

2차 시도 (에라토스테네스의 체)

function solution(n) {
  let jud = true;
  let answer = []; 
  for (let i=2; i<=n; i++) {
    for (let j=2; j<=Math.sqrt(i); j++) {
      // console.log(`${i}%${j}`);
      // console.log(i%(j))
      if (i%j===0) {
        jud=false; 
        break; 
      }
    }
    if (jud) {
      answer.push(i);
    }
    jud=true;
  }
  return answer.length; 
}

console.log(solution(10));

다른 풀이

set으로 홀수들을 일단 다 구해놓고 제곱에 해당하는 애들을 삭제하는 방식. 에라토스테네스의 체를 사용하되 set을 통해 거꾸로 구한듯?

function solution(n) {
  const s = new Set();
  for(let i=1; i<=n; i+=2){
      s.add(i);
  }
  console.log(s); // Set(5) { 1, 3, 5, 7, 9 }

  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);
           }
      }
  }
  console.log(s); // Set(4) { 3, 5, 7, 2 }
  return s.size;
}

console.log(solution(9));

신기하다.

function solution(n){
  let s= [...Array(n).keys()] // 배열을 만들고 그 key값들을 나열해서 또 다른 배열 생성
  //console.log(s); // [ 0, 1, 2, 3, 4, 5, 6, 7, 8 ]

  s[0]=0
  for(let i=2; i<=parseInt(n**.5)+1;i++){
    // console.log(i);

    for (let j=2 ; j<=(n-i)/i+1; j++){ // 소수가 아닌 애들은 0으로 바꾸기
      s[i*j-1]=0
    }
  }
  return s.filter(x=>Boolean(x)).length; // boolean으로 0인 애들을 거르기
}

console.log(solution(9));