[Q]프로그래머스 #JS - 소수찾기**

문제

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

풀이

다시 공부 시 참고 => 참고1
반드시 에라토스테네스의 체를 이용할 필요는 없다
참고2
참고3

0. 다른 사람의 풀이 => 효율성 실패하는 코드

function solution(n) {
    var result = 0;
    var cnt=0;
    for(var a=2;a<=n;a++){
    cnt=0;
    for(var b=1;b<=a;b++){
            if(a%b===0)
          cnt++;
    }
    if(cnt==2)
      result++;
  }
    return result;
}

1. 2020 => 실패한 코드 , 유사한 코드

// function solution(n) {
//     var answer = 0;
//     var count = 0;

//     if(n===2){
//       answer = 2;
//     } else {
//       for(var i=3; i<=n; i++){
//         for(var j=2; j<i; j++){
//           if(i%j === 0){
//             count = count +1;
//             break;
//           } 
//         }
//       }
//       answer = n-1-count;  
//     }
//     return answer;
// }

풀이과정 문제점

다른 사람의 풀이랑 나의 사고과정 큰 줄기는 같았는데, 가장 크게 다른 점 => (others)소수를 찾아서 count vs (me)소수가 아닌 것을 찾아서 전체에서 빼주기... => 왜 더 어렵게 접근?
2. 2019

function solution(n) {
    var answer = 0;
    var array1 = [];

    for(var i=1; i<=n; i++){
        array1[i] = true;
    }
  
  for(var j=2; j<Math.sqrt(n); j++){
    if(array1[j]){
      for(var x =j*j; x<=n; x+=j){
        array1[x]=false;
      }
    }
  }

  for(var y=2; y<=n; y++){
    if (array1[y] === true){
    answer = answer + 1;
    }
  }

    return answer;
}

function solution(n) {
  const primes = [];
  for (let j = 2; j <= n; j++) {
    let isPrime = true;
    const sqrt = Math.sqrt(j);
    for (let i = 0; primes[i] <= sqrt; i++) {
      if (j % primes[i] === 0) {
        isPrime = false;
        break;
      }
    }
    if (isPrime) {
      primes.push(j);
    };
  }
  return primes.length;
}

참고사항

에라토스테네스의 체