(Algorithm) Prime Number

Mirrer·2023년 1월 6일

algorithm

Algorithm

목록 보기

13/15

Prime Number

소수를 판별하는 Algorithm

소수(Prime Number)란 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수를 의미한다.

$6$ 은 $1, 2, 3, 6$ 으로 나누어져 소수가 아니다.

$7$ 은 $1$ 과 $7$ 을 제외하고 나누어지지 않으므로 소수이다.

특정 자연수의 소수 판별 과정을 코드로 구현하면 다음과 같다.

function isPrimeNumber(n) {
  for (let i = 2; i < n; i++) { // 2부터 (x - 1)까지의 모든 수를 확인
    if(n % i === 0) return false; // x가 해당 수로 나누어 떨어진다면 소수가 아니다.
  }
  return true; // 나누어진다면 소수
}

console.log(isPrimeNumber(7) ? '소수입니다.' : '소수가 아닙니다.');

Time Complexity

위와 같은 기본 소수 판별 알고리즘 코드는 $2$ 부터 $X-1$ 까지의 모든 자연수에 대하여 연산을 수행한다.

즉, 모든 수를 하나씩 확인하기 때문에 $O(X)$ 의 시간 복잡도를 가진다.

약수의 성질

약수는 다음과 같은 특징이 존재한다.

모든 약수는 가운데 약수를 기준으로 곱셈 연산에 대해 대칭된다.
즉, 특정 자연수의 모든 약수는 가운데 약수(제곱근)까지만 확인하면 된다.

이를 통해 기존 소수 판별 알고리즘을 개선하여 더 나은 시간 복잡도를 가진 코드를 구현할 수 있다.

약수의 성질을 이용하여 기존 코드를 개선하면 다음과 같다.

function isPrimeNumber(n) {
  // 부터 x의 제곱근까지의 모든 수를 확인
  for (let i = 2; i <= Math.floor(Math.sqrt(n)); i++) {
    if(n % i === 0) return false;
  }
  return true;
}

console.log(isPrimeNumber(7) ? '소수입니다.' : '소수가 아닙니다.');

Time Complexity

개선된 소수 판별 알고리즘은 $2$ 부터 $X$ 의 제곱근(소수점 이하 무시)까지 모든 자연수에 대하여 연산을 수행하므로 시간 복잡도는 $O(N^½)$ 이다.

Sieve of Eratosthenes

특정 범위에 있는 모든 소수들을 빠르게 판별하는 Algorithm

에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘은 다수의 자연수에 대하여 소수 여부를 판별할 때 사용하는 대표적인 알고리즘이다.

에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾을 때 사용 가능하며, 구체적인 동작 과정은 다음과 같다.

[Step 1]. 2부터 N까지의 모든 자연수를 나열
[Step 2]. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾음
[Step 3]. 남은 수 중에서 i의 배수를 모두 제거 (i는 제거하지 않음)
[Step 4]. 더 이상 반복할 수 없을 때까지 위의 과정을 반복

위 과정을 코드로 구현하면 다음과 같다.

const N = 10;
const arr = { 1: true };

// 2부터 n의 제곱근까지의 모든 수를 확인
for (let i = 2; i <= Math.ceil(Math.sqrt(N)); i++) {
  if (arr[i]) continue; // 이미 제거된 경우

  // n을 제외한 n의 배수부터 제거
  for (let j = i * i; j <= N; j += i) { 
    arr[j] = true;
  }
}

const result = [];
// 소수인 경우 (false) 결과 배열에 추가
for (let i = 2; i <= N; i++) {
  if (!arr[i]) result.push(i);
}

console.log(result.join(' '));