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

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

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

프로그래머스에 있는 문제다.

 

소수의 정의는 자기 자신과 1을 제외한 다른 수로 나누어지지 않는 수이다.

초기에 생각한 방법은 루트값보다 작은 수로만 직접 나누어 보는 것이다.
루트값 이전까지 나누어지지 않았다면 이후의 값들 또한 나누어지지 않기 때문이다.

unction solution1(n) {

  let answer = 0;

  for (let i = 2; i <= n; i++) {

    // 미리 더함

    answer += 1;

    for (let j = 2; j * j <= i; j++) {

      if (i % j == 0) {

        //console.log(j);

        answer -= 1;

        break;

      }

    }

  }

  return answer;

}

다만 이렇게 풀면 런타임 에러가 뜬다.

 

이를 해결하기 위한 방법이 에라토스테네스의_체이다.

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. 
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. 
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. 
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다. 

소수인 값들을 제외한 모든 수를 지우면서 진행하는 것이다.

 

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

이를 알고리즘으로 표현하면 아래와 같다.

function solution(nums) {
  const prime = new Array(nums + 1).fill(1);
  let count = nums - 1;
  for (let i = 2; i < Math.sqrt(nums); i++) {
    if (prime[i]) {

      for (let j = i ** 2; j <= nums; j += i) {
        if (prime[j]) count--, (prime[j] = 0);
      }
    }
  }
  console.log(count);
  return count;
}

우선 배열을 만들어서 값을 다 집어넣는다. (1에서 nums까지의 소수의 개수를 판별하는 문제임)
인덱스는 0부터 시작하기 떄문에 배열은 nums+1개로 만들고 fill함수를 통해서 전부다 1로 채워준다.

그리고 해당수의 제곱근보다 작은 수들에 대해서 확인을 한다.

배열에 있는 인덱스 값이 0이면 소수가 아니고, 1이면 최종적으로 소수이다. 하지만 1은 소수가 아니므로 count에서 미리 한 개를 뺀다.

예를 들어 10의 경우에는 i는 2부터 3까지만 실행된다 ( 10의 제곱근이 3.xxxx 이므로 )

 

이후 j를 통해서 i값의 제곱들만 거르기 시작한다. (이후 더 작은 j 값에서 자기보다 작은 값을 곱한 값을 걸렀기 때문이다.)
이후  i의 2배 3배 4배 형식으로 값을 확인하기 때문에 for문의 조건은 j+=i이다 

즉 i를 통해서 소수를 찾고 j를 통해서 해당 소수의 배수를 거르는 작업이다.

i가 2일때는 j에서 4를 거르고 이후 6 8 10을 걸러준다. ( 배열의 값을 0으로 만듬)
이후 3일 때는 9를 걸러준다. 
 최종적으로 배열이 11110101000 이 된다.  ( 0123 5 7의 값만 1이됨 )
이때 count는 거르는 작업에서 뺴줬기 떄문에 9개에서 5개를 뺸 4개가 되고. 1의 개수보단  배열의 2개가 적다(0과 1을 뺌)