[JavaScript] 소수 판별 - 에라토스테네스의 체

김형준·2025년 9월 16일

JavaScript js 소수 에라토스테네스 자바스크립트 판별

JavaScript

목록 보기

10/11

🟢 반복문 사용

1️⃣ 기본 반복문

시간 복잡도: O(n)

function isPrime(num) {
	if (num === 1) return false;
 	for (let i = 2; i < num; i++) {
  		if (num % i === 0) return false;
	} 
    return true;
}

2️⃣ 반복문 최적화

시간 복잡도: O(n/2) = O(n)

function isPrime(num) {
	if (num === 1) return false;
 	for (let i = 2; i < num / 2; i++) {
  		if (num % i === 0) return false;
	} 
    return true;
}

🟢 에라토스테네스의 체

시간 복잡도: O(√n)

아래 예시에서는 120 이하의 소수를 모두 찾고 있습니다.

로직은 다음과 같습니다.

2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
2는 소수이므로 Prime numbers에 넣는다.
2의 배수를 모두 지운다.
지워지지 않은 수 3을 Prime numbers에 넣는다.
3의 배수를 모두 지운다.
지워지지 않은 수 5를 Prime numbers에 넣는다.
5의 배수를 모두 지운다.
지워지지 않은 수 7을 Prime numbers에 넣는다.
7의 배수를 모두 지운다.
지워지지 않은 수 11을 Prime numbers에 넣는다.
11의 배수를 모두 지운다.
이때, 11 이후의 지워지지 않은 수 들은 전부 소수로 판별된다.

여기서 11은

11^2 > 120

에서 결정됩니다.

즉, n까지의 모든 소수를 구하기 위해서는 sqrt(n)보다 작은 수의 배수들만 지워도 됩니다.

1️⃣ num이 소수인지 판별하기

function isPrime(num) {
	if (num === 1) return false; 
 	for (let i = 2; i <= parseInt(Math.sqrt(num)); i++) {
  		if (num % i === 0) return false;
	} 
    return true; 
}

2️⃣ 1 ~ num까지의 소수 구하기

function isPrime(num) {
	let arr = Array(num + 1).fill(true); // index : 0 ~ num+1

    arr[0] = false;
    arr[1] = false;
    // 0, 1은 소수가 아님

    for (let i = 2; i * i <= num; i++) { // sqrt(num)까지 반복하는 것과 같음
        if (arr[i]) {
            for (let j = i * i; j <= num; j += i) {
                // i * 2 ~ i * (i - 1)까지의 값은 이미 판별됨
                arr[j] = false;
            }
        }
    }
    return arr // 값이 true인 것들이 소수
}

Reference

김형준

프론트엔드 개발자, 엔지니어 지망생

이전 포스트

[JavaScript] 최소 힙 (Min Heap) 구현

다음 포스트