프로그래머스 알고리즘#3 - 소수찾기

<문제>

<풀이>

function solution(n) {
    var answer = 0;
    var s;
    for (var i=2; i<=n ;i++){
        s=0;
        for(var j=2; j<=i; j++){
            if(i%j == 0) s++;
        }
        if(s == 1) answer++;
    }
    return answer;
}

라고 하면 테스트는 일부 통과하지만 뒷부분에서는 시간초과로 실패하고

효율성에서 완전 꽝이다.....

2부터 n까지 다 돌면서 확인하기때문에 비효율적일 수 밖에 없다.

효율적으로 소수를 구하는 공식이 따로 있는데, 에라토스테네스의 체를 이용하여 소수를 구하는 것이다.

 

에라토스테네스의 체

에라토스테네스의 체는 소수를 구하고자 하는 범위가 2~n일때 제곱근에 해당하는 범위안의 배수들을 계속 제외하면 결국 소수만 남게된다.

 

예를들어 n=120일때 120의 제곱근인 2~10까지의 소수에 대한 배수를 제외하면된다.

그럼 제곱근까지의 소수를 어떻게 알까?

겉 반복문 i는 2부터 진행하고 안 반복문 j는 i*i부터 진행하게 하면서 

i가 2일때 j반복문은 for(2*2 ; 2<=120 ; 2*2+2)이므로 j반복문에서 2는 해당이 되지 않는다.

거기에 +2씩 하면서 2의 배수를 찾아다니면서 false값을 넣어 소수가 아님을 표시해주는 것이다.

 

또 그 반복문을 if문이 감싸고 있는데 이 if문은 arr값이 true인 경우에만 검사를 하게 된다.

그 말은 i가 2인 반복문이 돌때 이미 4는 소수가 아닌 false값을 받았기때문에 아예 검사도 하지 않는 것이다.

이런식으로 이미 소수가 아니라는 검사를 받은 애들의 검사가 더 이루어지지 않기 때문에 효율성이 크게 높아지는 것이다.

function solution(n) {
  var arr=Array(n+1).fill(true).fill(false, 0, 2);
  
  for (var i=2; i<=n ;i++){
    if(arr[i]){
      for(var j=i*i; j<=n; j+=i){
      	arr[j] = false;
      }
    }
  }
  return arr.filter((ele)=>{return ele}).length;
}