JS 소수 판별법

JS에서 소수를 판별할 수 있는 방법은 총 3가지가 있다.

 

1. 모든 수로 나누어가며 판별하기

 

2. 각 숫자의 절반만큼만 나누어가며 판별하기

 

3. 각 숫자의 제곱근까지 나누어가며 판별하기

 

 

1번

일단 숫자가 2면 소수이므로 true로 리턴

 

그 후 각 숫자까지 모든 숫자로 나누어서 0이 되면 false로 리턴

 

해당하지 않으면 소수이므로 true리턴

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

시간복잡도 O(N)

 

2번

1번과 비슷한 방법이지만 숫자가 반으로 줄어들어 더 빠르게 돌릴 수 있다.

    function isPrime(num){
        if(num===2) return true;

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

시간복잡도 O(N)

3번

3번이 가장 효율적인데 그 수의 제곱근까지만 나누어보고 그 뒤는 안 나누는 방법이다.

제곱근보다 작은 수 에서 안나누어지면 제곱근보다 큰 수에서 나누어질 수가 없기 때문에 제곱근까지만 나누는 것이다.

    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;
    }

 

시간복잡도 O(√ N)