소수
이번 포스트에서는 소수(Prime number)에 대해 알아보도록 하겠습니다.
1. 소수란?
소수는 약수가 1과 자신 이외에는 없는 자연수를 나타냅니다.
때문에 자연수 $ N $이 소수가 되려면 2보다 크거나 같고 $ N-1 $ 보다 작거나 같은 자연수 중 나누어 나머지가 0이 되는 수가 존재해서는 안됩니다.
2. 소수 구하기
(1) Loop
가장 먼저 떠올릴 수 있는 방법은 2부터 $ N-1 $까지 순차적으로 확인 해 보는 방법이 있습니다.
function isPrime(number) {
if (number < 2) return false;
for (let i = 2; i < number; i++) {
if (number % i === 0) return false;
}
return true;
}이 함수의 시간 복잡도는 $ O(N) $ 입니다.
혹시 더 줄일 수 있을까요?
$ N $이 소수가 아닐 때 $ N = a \times b ( a \le b) $ 로 나타낼 수 있습니다.
$ a , b $ 두 수의 차가 가장 작은 경우는 $ a = b $ 인 $ a $ 가 $ \sqrt{N} $ 인 Case입니다.
$ \sqrt{N} $ 인 경우 나누어지는 두 수 $ a, b $ 중 작은 수 $ a $ 가 가능한 범위 중 최대값이기 때문에 해당 값 $ \sqrt{N} $ 까지만 검사해 주면 되겠습니다.
function isPrime(number) {
if (number < 2) return false;
for (let i = 2; i ** 2 <= number; i++) {
if (number % i === 0) return false;
}
return true;
}프로그래밍 언어에서 실수 값은 근사 값을 나타내기에 정확한 계산을 위해 조건의 양변을 제곱해 주어 $ i ** 2 <= number $ 로 작성 해줍시다.
이 함수의 시간 복잡도는 $ O(\sqrt{N}) $ 까지 줄어들게 됩니다.
(2) 에라토스테네스의 체
하지만 수 하나의 소수 여부가 아닌 범위 내의 모든 소수를 구하는 시나리오라면 어떻게 될까요?
$N$ 개의 수가 있는 범위의 소수를 구하게 된다면 각각의 수가 소수인지 여부를 확인해야 하기에 $ O(N\sqrt{N}) $ 로 시간 복잡도가 커집니다.
이때 에라토스테네스의 체 (Sieve of Eratosthenes) 알고리즘을 활용하면 커진 시간 복잡도를 크게 줄일 수 있습니다.
에라토스테네스의 체로 $ N $ 보다 작은 모든 소수를 구하는 문제를 풀어보겠습니다.
- N 크기만큼의 배열을 선언하고 2부터 $ N $ 까지 모든 수를 채워 넣습니다.
- 지워지지 않은 수 중 가장 작은 수를 찾습니다.
- 해당 수는 소수입니다.
- 배열 내 해당 수의 모든 배수를 지웁니다.
- 다음 인덱스로 넘어가 2 ~ 4 단계를 반복하되 현재 인덱스의 수가 지워진 수이면 다음 인덱스로 이동합니다.
단계의 반복은 현재 인덱스의 수가 $ \sqrt{N} $ 보다 크지 않을 때까지 반복합니다.
모든 단계 종료 후 배열에는 소수만 남게 됩니다.
function getGroupOfPrimeNumbersLeastThanNumber(number) {
const sieve = Array.from({
length: number + 1,
}, () => true)
sieve[0] = false;
sieve[1] = false;
for (let i = 2; i * i <= number; i++) {
if (!sieve) continue;
for (let j = i * 2; j <= number; j += i) {
sieve[j] = false
}
}
const groupOfPrimeNumbers = [];
sieve.forEach((val, index) => {
if(val) groupOfPrimeNumbers.push(index);
})
return groupOfPrimeNumbers
}에라토스테네스의 체의 시간복잡도는 $ O(Nlog(logN)) $ 으로 선형이라고 할 수 있을 만큼 빠릅니다.
마치며
이번 포스트에서는 소수를 구하는 두 가지 방법을 알아보았는데요.
두 가지 방법 모두 각자의 장단점을 가지고 있습니다.
반복법은 적은 개수의 소수를 구할 때, 에라토스테네스의 체는 넓은 범위의 소수들을 구할 때 사용하는 것이 좋습니다.
때문에 문제에 주어진 조건에 맞추어 적절한 선택을 해서 사용하도록 합시다.