[알고리즘] 소수 판별하기 - 여러가지 방법의 소수 판별법 by javascript

앞서 "[알고리즘] 소수 찾기 - 에라토스테네스의 체 by javascript" 라는 제목의 소수 찾기 알고리즘을 정리하였는데,

지금 까지 소수 찾기 및 소수 판별에 있어 전부 에라토스테네스의 체 코드를 사용하여 리스트를 뽑고 그 안에 포함되어있는 지를 체크해왔다.

하지만 역시 자바스크립트는 자바스크립트... RangeError: invalid array length 에러가 발생하면 그 방식을 사용할 수 없었다.

(당연하게도 소수 찾는 방식으로 사용한걸 단순히 하나의 숫자에 대한 소수 판별에, 사용하는 데에는 제약사항이 있을 수 있다는 걸 간과했다.)

그래서 이제 소수 판별하는 여러가지 방법에 대해 알아보고자 한다.

1. 단순하게 모든 수를 판별하기

const isPrime = (num) => {
    if(!num || num === 1) return false;
    for (let i = 2; i < num; i++) {
        if (num % i === 0) return false;
    }

    return true;
}

1이 아닌 2부터 n사이의 모든 정수를 다 나누어, 조건에 일치하는 수가 있는지 확인하는 방법이다.

당연하게도 숫자가 커질수록 점점 오래 걸리기 때문에 많이 사용되지는 않는다.

2. 주어진 수의 절반만 판별하기

const isPrime = (num) => {
    if(!num || num === 1) return false;
    for (let i = 2; i <= num/2 ; i++) {
        if (num % i === 0) return false;
    }

    return true;
}

그냥 단순하게 1번 방법에서 절반으로 줄인것이다.

num의 약수는 num의 절반을 넘을 수 없기 때문에 num/2가 성립되는것이다.

하지만 1번보다 빠를뿐 더 좋은 성능의 코드들이 존재한다.

3. 제곱근(Math.sqrt) 사용하기(★)

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의 제곱근보다 큰 수에서도 나눠지는 수가 나올 수 없기 때문에, 굳이 제곱근보다 큰 수까지 반복문을 돌릴 필요가 없다고한다.