숫자 n까지의 소수 찾기 (자바스크립트)

August 27th 2018

이전에 특정 수의 가장 큰 소인수를 찾는 방법을 포스팅했었습니다. 이번에는 주어진 수 n까지 소수의 개수 찾는 방법에 대해 알아보도록 하겠습니다.

Contents

소수란? (Prime factor)
주어진 수가 소수인지 확인하는 방법
소수의 개수 구하는 방법
에라토스테네스의 체
추가 최적화 방법

소수란?(Prime factor)

소수란 약수로 1과 자기 자신만을 가지는 수입니다.
0과 1은 소수가 아닙니다.
따라서, 1보다 크고 자기 자신보다 작은 수로 나누어 떨어지면 소수가 아닙니다.

주어진 수가 소수인지 확인하는 방법

위에서 소수의 정의에 대해 살펴봤습니다. 이를 기준으로 이번에는 특정 수가 주어졌을 때, 이 수가 소수인지 아닌지 확인하는 방법에 대해 알아보도록 하겠습니다. 별도의 함수를 작성해 소수인면 true, 소수가 아니면 false를 반환하도록 작성하고자 합니다.

function isPrime(n) {
  if (n === 2) {
    // 숫자 2는 소수이므로 true를 반환함.
    return true;
  }

  if (n < 2 || !(n % 2)) {
    // 0, 1과 2의 배수는 false로 반환함.
    return false;
  }

  for (let i = 3; i <= Math.sqrt(n); i += 2) {
    // 3부터 루트 n 까지의 숫자 중 나누어 떨어지면 false 반환함.
    if (n % i === 0) {
      return false;
    }
  }

  return true;
}

소수의 개수 구하는 방법

가장 간단한 방법은 2부터 '특정 수 - 1'까지 반복문을 실행 시킵니다. 반복문 중 해당하는 수가 어떠한 수로 나누어 떨어지면 소수가 아닙니다. 이때, 위에서 만든 isPrime 함수를 사용할 수도 있을 것입니다.

하지만, 이 방식의 문제점은 숫자 n이 커질수록 연산 횟수가 기하급수적으로 증가합니다. 이 문제를 해결하기 위해서는 다른 방법을 이용해야 합니다. 저는 여러 방법 중 소수의 개수를 구할 때 많이 이용하는 에라토스테네스의 체를 이용해 해결하는 방법에 대해 학습하고자 합니다.

에라토스테네스의 체

에라토스테네스의 체는 숫자 n까지의 소수의 개수를 구할 때, 가장 작은 소수부터 시작해 그 수의 배수를 제거해가며 소수의 개수를 구하는 방법입니다. 예를 들면, 2를 제외한 2의 배수를 제거하고, 그다음 3을 제외한 3의 배수를 제거, 5를 제외한 5의 배수를 제거해 가며 소수를 구하는 방법입니다. 이런 방식으로 문제를 풀면 체크해야하는 수의 범위를 현저히 줄일 수 있습니다. 다시 말해 컴퓨터의 연산 과정을 줄일 수가 있게 됩니다.

function solution(limit) {
  const primes = [];
  const bools = new Array(limit - 1).fill(true); // 배열의 index 0은 숫자 2를 대신하고 index 1은 숫자 3, index 2는 4를...

  for (let i = 2; i < limit; i++) {
    // 1은 소수가 아니기 때문에 반복문을 2부터 시작해 합성수의 값을 false로 변경함.
    if (bools[i - 2]) {
      for (let j = i * 2; j <= limit; j += i) {
        bools[j - 2] = false;
      }
    }
  }

  for (let v = 0; v < bools.length; v++) {
    // 소수로 남아있는 bools 배열의 요소만 취해, 소수만의 배열을 생성함.
    if (bools[v]) {
      primes.push(v + 2);
    }
  }

  return primes;
}

추가 최적화 방법

첫 번째 반복문에서 숫자 n까지 loop을 돌릴 필요없이, √limit 까지만 반복문을 실행할 수 있습니다.
처음 boolean 값을 가지는 배열을 생성할 때, 2의 배수는 소수가 아니기 때문에 저장할 필요가 없습니다. 하지만, 2의 배수를 저장하지 않으면 저장하는 Data의 길이를 줄일 수 있지만, 다른 연산 작업이 복잡하고 여려워 질 것 같습니다. 더 나은 방법 아시는 분 알려주시면 커피 한 잔 사드리겠습니다. :)

Handmade with .