[JS] 약수 구하기, 이 숫자가 소수인가요, 1부터 N까지의 소수구하기

약수구하기

 

코딩 테스트에서 약수 구하기 문제가 나오면 무조건 Math.sqrt(n)(제곱근)까지만 반복하는 알고리즘을 쓰셔야 합니다.

1부터 n까지 전부 나누는 방식은 $O(N)$이라 숫자가 커지면 시간 초과가 발생합니다. 제곱근 방식을 쓰면 시간 복잡도가 $O(\sqrt{N})$으로 획기적으로 줄어듭니다.

가장 정석적이고 쉬운 알고리즘 패턴을 정리해 드립니다.

---

핵심 알고리즘: 제곱근까지만 탐색하기

원리는 간단합니다. 약수는 항상 **짝(Pair)**으로 존재하기 때문입니다.

예를 들어 100의 약수를 구할 때, $1 \times 100$, $2 \times 50$, $4 \times 25$... 식으로 짝이 맞습니다. 따라서 작은 수 쪽만 찾으면 큰 수 쪽은 계산으로 바로 구할 수 있습니다.

JavaScript 표준 코드

이 코드를 그대로 외우거나 저장해 두시는 것을 추천합니다.

JavaScript

 

function getDivisors(num) {
    const divisors = [];
    
    // 1. 1부터 제곱근까지만 반복 (i * i <= num 과 동일)
    for(let i = 1; i <= Math.sqrt(num); i++) {
        
        // 2. 약수인지 확인
        if(num % i === 0) {
            divisors.push(i); // 작은 약수 추가
            
            // 3. 짝이 되는 큰 약수 추가 (중복 방지: 5x5=25 같은 경우)
            if(i !== num / i) {
                divisors.push(num / i);
            }
        }
    }
    
    // 4. (선택) 오름차순 정렬 - 코테에서는 보통 정렬을 요구함
    return divisors.sort((a, b) => a - b);
}

// 테스트
console.log(getDivisors(100)); 
// 결과: [1, 2, 4, 5, 10, 20, 25, 50, 100]

---

코드 작성 시 주의할 점 (실수 포인트)

1. 반복 조건: i <= Math.sqrt(num) 혹은 i * i <= num으로 설정해야 합니다. 등호(=)를 빼먹으면 완전 제곱수(예: 25, 36 등)의 약수 하나가 빠집니다.
2. 중복 제거: if (i !== num / i) 조건이 없으면, 25의 약수를 구할 때 5가 두 번 들어갑니다.
3. 정렬: 위 알고리즘은 순서대로(1, 100, 2, 50...) 들어가기 때문에, 문제에서 오름차순을 요구하면 마지막에 꼭 .sort((a, b) => a - b)를 해줘야 합니다.

왜 이 방식이 유리한가요?

• 일반 반복문 ($O(N)$): 10억(1,000,000,000)을 입력받으면 반복문이 10억 번 돕니다. (시간 초과 100%)
• 제곱근 반복문 ($O(\sqrt{N})$): 10억을 입력받아도 $\sqrt{10억} \approx$ 31,622번만 돌면 끝납니다. 속도 차이가 엄청납니다.

 

(1) N값이 소수인가요? (2) 1부터 N까지의 소수를 모두 구하세요

 

소수(Prime Number) 구하기는 약수 구하기와 원리가 완전히 똑같습니다. 딱 두 가지 패턴만 기억하면 코딩 테스트의 99%는 커버됩니다.

상황에 따라 쓰는 알고리즘이 다르니 구분해서 알아두셔야 합니다.

---

상황 1: "이 숫자 하나가 소수인가요?" (단건 판별)

약수 구할 때와 마찬가지로 $\sqrt{N}$까지만 나누어 보면 됩니다.

만약 $\sqrt{N}$까지 나누어 떨어지는 수가 하나도 없다면, 그 수는 소수입니다.

시간 복잡도: $O(\sqrt{N})$

JavaScript

 

function isPrime(num) {
    // 0과 1은 소수가 아님 (가장 많이 하는 실수!)
    if (num <= 1) return false;
    
    // 2부터 제곱근까지만 확인
    for (let i = 2; i <= Math.sqrt(num); i++) {
        // 나누어 떨어지면 약수가 있다는 뜻 -> 소수 아님
        if (num % i === 0) return false; 
    }
    
    // 끝까지 살아남았으면 소수
    return true;
}

console.log(isPrime(97)); // true
console.log(isPrime(100)); // false

---

상황 2: "1부터 N까지 소수를 전부 찾아라" (범위 판별)

이때 isPrime 함수를 N번 돌리면 시간이 너무 오래 걸립니다. 이때는 고대 그리스 수학자가 만든 필승법인 **'에라토스테네스의 체'**를 써야 합니다.

핵심 원리: 소수를 찾으면 그 소수의 배수들을 싹 다 지워나가는 방식입니다.

시간 복잡도: $O(N \log \log N)$ (사실상 $O(N)$에 가까울 정도로 엄청나게 빠름)

JavaScript

 

function getPrimesRange(n) {
    // 1. 일단 모두 소수(true)라고 가정하고 배열 생성 (0번 인덱스 포함 n+1개)
    const isPrime = new Array(n + 1).fill(true);
    
    // 0과 1은 소수가 아님
    isPrime[0] = false;
    isPrime[1] = false;
    
    // 2. 2부터 제곱근까지만 반복 (약수 원리 동일)
    for (let i = 2; i <= Math.sqrt(n); i++) {
        
        // 만약 i가 소수라면 (아직 지워지지 않았다면)
        if (isPrime[i]) {
            // i의 배수들을 모두 false 처리 (i * i 부터 시작하면 더 효율적)
            for (let j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    
    // 3. true인 인덱스(소수)만 뽑아내기 (선택 사항)
    /* 결과 배열을 리턴하거나, 개수를 세거나 문제에 따라 다름
       여기서는 소수 숫자만 담아서 리턴 
    */
    const results = [];
    for(let i = 2; i <= n; i++){
        if(isPrime[i]) results.push(i);
    }
    return results;
}

console.log(getPrimesRange(20)); 
// 결과: [2, 3, 5, 7, 11, 13, 17, 19]

---

💡 코테 실전 팁 (무조건 외우세요)

1. 0과 1 처리: if (num <= 1) return false; 이 코드는 무조건 제일 먼저 넣으세요. 이거 안 넣어서 테스트 케이스 몇 개 틀리는 경우가 정말 많습니다.
2. 에라토스테네스의 체 최적화: 안쪽 반복문(j)을 돌릴 때 let j = i * 2가 아니라 let j = i * i 부터 시작해도 됩니다. (그 이전 배수들은 이미 더 작은 소수들에 의해 지워졌기 때문입니다.)
3. 언제 무엇을 쓰는가?
   • 숫자 하나가 소수인지 궁금할 때: 상황 1 코드
   • 여러 개의 소수를 구하거나, 범위 내 소수 개수를 구할 때: 상황 2 코드

이 두 가지 코드만 템플릿처럼 가지고 계시면 소수 문제는 다 풀 수 있습니다.