TIL
[클라우딩 어플리케이션 엔지니어링 TIL] - DAY 19
blackmilktea
2024. 5. 10. 19:12
소수 판별하기
현재 숫자가 소수인지 판별하는 알고리즘을 작성할 때
가장 단순한 방법은 n까지 반복문을 돌면서 1 이외의 약수가 있는지 확인하는 것이다.
function isPrime(n) {
for (let i = 2; i < n; i++) {
if (n % i == 0) return false;
}
return true;
}이 알고리즘의 시간복잡도는 O(n) 여기서 조금 최적화를 해보자면
특정 수의 약수는 가운데 약수를 기준으로 대칭성을 가지므로 제곱근까지만 확인해 보면 된다.
- ex) 16 => 1, 2, 4, 8, 16
- 1 x 16 = 16
- 2 x 8 = 16
- 4 x 4 = 16
function isPrime(n) {
for (let i = 2; i * i <= n; i++) {
if (num % i == 0) return false;
}
return true;
}최적화한 알고리즘의 시간복잡도는 O(sqrt(n))
여기서 더 최적화할 수도 있지만 판별해야 할 수가 많지 않을 땐 이런 단순한 코드로도 충분하고,
많은 수를 판별해야 할 때는 여기서 더 최적화를 해봐야 크게 의미가 없다.
따라서 특정 범위 또는 많은 수를 판별해야 할 때는 에라토스테네스의 체를 이용해 소수를 판별한다.
에라토스테네스의 체
- 2부터 소수를 구하고자 하는 구간의 모든 수를 나열, 나열한 수는 전부 소수(true)라고 가정
- 현재 숫자가 소수인지 확인
- 소수(true)면 자기 자신을 제외하고 구간 내 자신의 배수를 모두 제거(false)
- 다움 숫자가 소수인지 확인하고, 소수(true)면 3번 반복 아니면(false) 다음 숫자 확인
- 위 과정을 반복하면 구하는 구간의 모든 소수가 남는다.
function get_primes(num) {
const prime = [false, false, ...Array(num - 1).fill(true)];
// 0과 1은 소수가 아니기에 미리 false로 체크
for (let i = 2; i * i <= num; i += 1) {
if (prime[i]) {
for (let j = i * 2; j <= num; j += i) {
prime[j] = false;
}
}
}
return prime.filter(Boolean);
}에라토스테네스의 체는 ㄴO(n log log n)으로 빠르지만 메모리가 많이 필요하다는 단점이 있다.