에라토스테네스의 체란?
에라토스테네스의 체(Sieve of Eratosthenes) 는 주어진 범위 내에서 모든 소수를 빠르게 찾는 알고리즘이다. 이 방법은 소수를 걸러내는 방식으로 동작하며, O(n log log n) 의 시간 복잡도를 가진다.
1. O(n log log n) 시간 복잡도의 소수 판별
JavaScript 코드:
function sieve(n) {
let sieve = new Array(n + 1).fill(true);
sieve[0] = sieve[1] = false;
for (let i = 2; i * i <= n; i++) {
if (sieve[i]) {
for (let k = i * i; k <= n; k += i) {
sieve[k] = false;
}
}
}
return sieve;
}
이 방법을 통해 n 이하의 모든 소수를 찾을 수 있다.
2. 소인수 분해 (Factorization)
소인수 분해는 정수를 소수의 곱으로 표현하는 과정 이다.
JavaScript 코드:
function sieve(n) {
// n까지의 모든 수에 대해, spf[i]를 i로 초기화
const spf = new Array(n + 1);
for (let i = 0; i <= n; i++) {
spf[i] = i;
}
// 0과 1은 소수가 아님
spf[0] = 0;
spf[1] = 1;
// 2부터 √n 까지의 수에 대해 최소 소인수를 업데이트
for (let i = 2; i * i <= n; i++) {
if (spf[i] === i) { // i가 소수라면
for (let j = i * i; j <= n; j += i) {
// 아직 j의 최소 소인수가 결정되지 않았다면, i로 설정
if (spf[j] === j) {
spf[j] = i;
}
}
}
}
return spf;
}
function factorization(x) {
// x에 대한 SPF 배열 생성
const spf = sieve(x);
const factors = [];
// x가 1이 될 때까지 소인수로 나누기
while (x !== 1) {
factors.push(spf[x]);
x = Math.floor(x / spf[x]);
}
return factors;
}
// 예시
console.log(factorization(24)); // 출력: [2, 2, 2, 3] (24 = 2 * 2 * 2 * 3)
console.log(factorization(60)); // 출력: [2, 2, 3, 5] (60 = 2 * 2 * 3 * 5)
이 방법을 사용하면 O(log x) 시간 복잡도로 소인수 분해가 가능하다.
소수만 출력하려면 아래 코드
function sieve(n) {
const spf = new Array(n + 1);
for (let i = 0; i <= n; i++) {
spf[i] = i;
}
spf[0] = 0;
spf[1] = 1;
for (let i = 2; i * i <= n; i++) {
if (spf[i] === i) { // i가 소수이면
for (let j = i * i; j <= n; j += i) {
if (spf[j] === j) {
spf[j] = i;
}
}
}
}
return spf;
}
function factorization(x) {
const spf = sieve(x);
const factorsSet = new Set(); // 중복 제거를 위한 Set 사용
while (x !== 1) {
factorsSet.add(spf[x]);
x = Math.floor(x / spf[x]);
}
return Array.from(factorsSet);
}
// 예제 테스트
console.log(factorization(24)); // 출력: [2, 3] (24 = 2*2*2*3)
console.log(factorization(60)); // 출력: [2, 3, 5] (60 = 2*2*3*5)
반응형
댓글