프로그래머스 소수 찾기 (JS) - 에라토스테네스의 체

소수찾기 문제

소수찾기 문제... 무식하게 풀었더니 역시 또 효율성 테스트에서 거부를 당했다. 뜨흑흑 정말 고민고민해서 잘 풀었다고 생각했는데 TㅇT

그래서 구글링하던 중에 에라토스테네스의 체 라는 방법이 효율적이라는 얘기를 주워듣고 이 기회에 이 알고리즘이 뭔지도 겸사겸사 공부해보았다.

일단 에라토스테네스의 체를 잘 정리해놓은 백준 문제 2960번이 있어서 이 문제를 참고해서 구현해보았다!

에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.

1. 2부터 N까지 모든 정수를 적는다.
2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

정말 이대로만 구현하면 된다...!

function solution(n) {
    var answer = 0;
    const prime = [];
    const arr = Array(n).fill(0);
    
    
    for(let i = 2; i <= n; i++){
        arr[i] = i;
    }
    
    for(let i = 2; i <= n; i++){
        if(arr[i] === 0) continue;
        prime.push(i);
        arr[i] = 0;
        
        for(let j = i * 2; j <= n; j += i){
            if(arr[j] === 0) continue;
            arr[j] = 0;
        }
    }
    
    answer = prime.length;
    
    return answer;
}

우선, 소수를 담을 배열 prime을 하나 만들었다.
또, 2부터 N까지의 모든 정수를 담을 배열 arr을 만들었다. 초기값은 0으로 모두 초기화를 해놓은 상태이고 배열의 길이도 n에 맞추었다.

 for(let i = 2; i <= n; i++){
   arr[i] = i;
 }

일단 소수는 2부터 체크하면 되기 때문에 반복문을 사용했다. arr[i] = i 와 같이 작성하여 만들어놓은 배열에 2부터 n까지 값을 넣어주었다.
여기서 2번째부터 값을 넣어주었으므로 0번째 인덱스와 1번째 인덱스는 0으로 남아있기 때문에 이후 반복문에서 continue를 사용한 것을 확인할 수 있다.

for(let i = 2; i <= n; i++){
  if(arr[i] === 0) continue;
  prime.push(i);
  arr[i] = 0;

  for(let j = i * 2; j <= n; j += i){
    if(arr[j] === 0) continue;
    arr[j] = 0;
  }
}

이 부분이 소수를 찾는 핵심 코드이다.
일단 기존 arr 배열이 0인 경우 continue 하도록 했고 그렇지 않을 때만 prime에 i값을 push 하도록 했다.
에라토스테네스의 체에 의하면 지우지 않은 수 중 가장 작은 수를 넣으면 된다고 했기 때문이다.
그리고 이 숫자를 이미 prime 배열에 push 했으므로 해당 인덱스는 0으로 바꿔주었다.

두번째 내부 반복문의 경우 i값의 배수인 경우에 모조리 arr 배열의 값을 0으로 만들어 버린다.
이러면 i의 배수인 경우 0이 되기 때문에 자연스럽게 소수가 아닌 수를 거를 수 있다.

그리고 다시 바깥 for문에 도착해서 i가 3이 되어 해당 동작을 반복하게 되고 결국 prime 배열에는 소수만 남게된다.

소수 배열의 길이를 return 해주면 끝!

누구에겐 쉬운 문제일지라도 하나하나 풀때마다 성취감이 정말정말 크다!
아직 솔루션을 찾아야 풀 수 있는 문제들도, 봐도 못푸는 문제들도 많지만 차근차근 자료구조랑 병행해서 공부해서 이전에 오랜 시간 고민해서 겨우 풀었던 문제도 고민없이 풀어버리고 더 어려운 문제를 만났을 때도 막힘없이 풀 수 있었으면 좋겠다. ㅎㅎ (미래의 나에게.....)