에라토스테네스의 체(소수구하기)

ㅃ :raising_hand: 알고리즘 공부 간 기록이 필요한 문제들에 대한 정리를 기록하는 포스트 입니다.

1. 소수

먼저 소수에 대한 정의를 살펴볼 필요가 있다.

  • 소수는 1과 자기 자신으로만 나누어지는 수 이다.
  • 1은 소수가 아니다.
  • 모든 자연수는 소수들의 곱으로 표현된다.

위 개념을 통해 에라토스테네스의 체 알고리즘을 알아보도록 한다.

2. 에라토스테네스의 체란?

그럼 에라토스테네스의 체 가 무엇인지 알아보면 아래와 같다.

264D383952BCC9CC31

주어진 숫자의 n의 제곱근 즉, 루트(n)의 값보다 작은 수의 배수를 모조리 n 보다 작은 범위에서 제거하면 된다는 개념을 가지고 있다.

자세한 개념은 아래 위키에서 확인하면 되며, 그럼 코드를 통해 확인해본 결과를 통해 조금 더 이해할 수 있도록 정리해보자.

2. 코드

function PrimeNumbers(n) {
  // 주어진 n 개의 true 값으로 채워진 배열을 만들고 0,1 은 false 로 변경
  let arr = Array(n + 1)
    .fill(true)
    .fill(false, 0, 2);

  // 소수가 아닌 것들을 false 로 변경
  for (let i = 2; i * i <= n; i++) {
    if (arr[i]) {
      for (let j = i * i; j <= n; j += i) {
        arr[j] = false;
      }
    }
  }
}

3. 결과정리

먼저

Array(n + 1)
  .fill(true)
  .fill(false, 0, 2);

위 코드를 통해 0 부터 n 까지의 숫자를 의미하는 배열을 만들고 각 index 값을 true 로 셋팅한다. 그리고 0과 1은 소수가 아니므로 false 로 치환한다.

// 소수가 아닌 것들을 false 로 변경
for (let i = 2; i * i <= n; i++) {
  if (arr[i]) {
    for (let j = i * i; j <= n; j += i) {
      arr[j] = false;
    }
  }
}

여기서 true / false 의 의미는 각 index 가 의미하는 숫자가 소수인지 아닌지 를 알려주는 것이다.

그럼 결과적으로 0 ~ n 까지만큼의 배열이 만들어져있고 0,1 번째만 false 로 값이 변경된 배열을 셋팅할 수 있다.

그후 반복문으로 들어가게 되는데 처음 시작은 2 부터 시작하므로 i=2 로 셋팅하고 제곱수가 주어진 n 의 값 보다 작거나 같은경우 true/false 를 확인한다.

여기까지 통과가 되면 해당 숫자 i 는 소수로 인정하며 이후 i 의 배수를 제거(false 로 변경) 하는 작업을 진행한다.

즉, 2의 제곱 수 4 가 j 가 되고 j는 n보다 작은 수 이므로 arr[4] 는 false 로 변경된 후 j += i 을통해 6,8,10 이 지워지게 된다. 이렇게 되면 그다음 i값은 3이 되고 그다음은 4이지만 이미 2 의 배수로 지워졌기 때문에 소수가 아니라 판별하고 5 로 넘어가게 된다.

이런식으로 n 보다 작은 각 배수들을 지워나가다 보면 결국 true 로 남아 있는 index 가 의미하는 숫자가 Prime Number 즉 소수가 되는 것이다.

참고 사이트

You may also enjoy