프로그래머스 1단계 - 소수 찾기

소수 찾기

---

문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

제한 조건

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

입출력 예시

n	result
10	4
5	3

---

🧀내가 한 풀이

처음 시도한 풀이... 다른부분에서는 통과하지만, 효율성 검사에서 자꾸 걸렸다...

//효율성에서 자꾸 걸림.. 
function solution(n) {
    var answer = 0;
    for(let i = 2; i <= n; i++){
        let num = true;
        for(let j = 2; j <= Math.sqrt(i); j++){
            if(i % j == 0) 
                num = false;
        }
        if(num) answer++;
    }
    return answer;
}

🧀내가 한 풀이2...

결국 다른 분들이 해결한 풀이 법을 참고해서 한 코드... 에라토스테네스의 체를 활용하여서 해결하였다...
소수의 배수들을 제거해나가면 결국 소수만 남는 방식이라고 한다.

//에라토스테네스의 체 사용 풀이
function solution(n) {
    var answer = [];
    for(var i = 0; i <= n; i++){
        answer.push(true);
    }
    answer[0] = false;
    answer[1] = false;
    
    for(var i = 2; i <= n; i++){
        if (answer[i]){
            for(let j = 2; j <= n/i; j++){
                answer[i*j] = false;
            }
        }
    }
    return answer.filter(el => el === true).length;
}

🧀다른 풀이

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