소수 판별하기

소수?

소수는 1과 자기 자신만을 약수로 가지는 수

ex) 3의 약수는 1 & 3

알고리즘을 풀다보니 소수 구하는 문제가 종종 나온다.
소수를 판별하는 다양한 방법을 정리해보자 !

소수 찾는 방법

1. 모든 수 확인하기

const isPrime = (num) => {
    // 1은 소수가 아님
    if(!num || num === 1) return false

    // n과 2부터 n - 1 까지의 나머지를 확인한다.
    for(let i = 2; i < num; i++){
        if(num % i === 0)return false
    }

    return true
}

2부터 주어진 수 - 1 까지의 모든 수를 확인한다.
가장 쉽고, 단순하지만 시간이 오래 걸리는 방법이다.

2. 절반만 확인하기

2-1. 짝수 제외

const isPrime = (num) => {
    if(!num || num === 1)return false

    // 3부터 홀수만 확인하기
    for(let i = 3; i < num; i += 2){
        if(num % i === 0)return false
    }

    return true
}

2를 제외한 짝수는 모두 소수가 아니다. 절반을 제외하는 첫번째 방법…

2-2. 1/2 제외

const isPrime = (num) => {
    if(!num || num === 1)return false

    // num의 절반까지 확인하기
    for(let i = 2; i <= num / 2 ; i++){
        if(num % i === 0)return false
    }

    return true
}

num 의 약수는 num 의 절반을 넘을 수 없다.
2-1 과 2-2 를 결합하면 탐색의 1/4 을 줄일 수 있다.
하지만, 더 확실하고 좋은 성능의 코드가 있다.

3. 제곱근 활용

const isPrime = (num) => {
    if(!num || num === 1)return false

    // 제곱근까지 확인하기
    for(let i = 2; i <= Math.sqrt(num); i++){
        if(num % i === 0)return false
    }

    return true
}

제곱근을 사용한 소수 판별.
num의 제곱근보다 작은 수에서 약수가 안나온다면 num의 제곱근보다 큰 수에서도 약수가 나올 수 없다.

4. 에라토스테네스의 체

하나의 수를 판별하는 방법이 아닌, 구간 내 소수를 확인하는 방법이다. 3번의 제곱근을 활용한 방법과 비슷하다. 주어진 값보다 큰 제곱수를 찾고 그 수의 제곱근보다 작은 수들의 배수를 지우면 남는 수는 소수가 된다.

예시는 120까지의 수 중에서 소수인 수를 찾는 문제다.
120 보다 큰 제곱인 수는 121 (11**2) 이다. 11 보다 작은 소수들의 배수를 찾아 지우면 남는 수는 모두 소수가 된다. JS로 구현해보자 !

const Eratos = (n) => {
    // 배열 만들기
    // 0과 1은 소수가 아니므로 false로 처리해둠
    let field = Array(n + 1).fill(true).fill(false, 0, 2)

    // 2부터 소수의 배수를 false 처리
    for(let i = 2; i * i <= n; i++){
        if(field[i]){
            for(let j = i * i; j <= n; j += i){
                field[j] = false
            }
        }
    }

    return field
}

const isPrimes = Eratos(120)

// 소수의 개수 구하기
isPrimes.filter(e => e).length
// 30

// 소수 반환하기
isPrimes.map((el, i) => el ? i : 0).filter(e => e)
// [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113 ]

소수를 찾는 방법을 정리해봤다.
나중에 소수 찾는 방법이 나오면 이 기억을 떠올리자 !

참고
나무위키

소수?
소수 찾는 방법