소수 판별하는 방법 [자바스크립트 알고리즘]

javascript 로 소수 구하는 방법

 

 

소수는

 

1과 자신만으로만 나누어서 나머지값이 0 인 (나누어 떨어지는)

1보다 큰 양의 정수를 말한다.

 

여기서 1 과 음수는 소수가 아니다.

 

 

소수 판별하는 방법중에 먼저 단순한 방법

 

 

모든 수를 판별하는 방법

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

    return true;
}

1이면 바로 false를 retrurn 시키고 아니면,

2부터 num 까지의 수를 전부 반복해서,

조건에 일치하는 수가 있는지 확인한다.

 

하지만 모든 수를 돌려야하기 때문에 num 값이 커지면 시간복잡도 문제로 좋지 않다.

 

 

 

절반만 돌리는 방법

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

    return true;
}

num 의 약수는 자신의 절반을 넘을 수 없다.

약수구하는 법은 하단링크참조

약수 구하는 방법 [자바스크립트 알고리즘]

첫번재의 모든 수를 돌려서 판별하는 것보다 퍼포먼스가 좋아졌다.

하지만 더 좋은 방법이 있다.

 

 

 

제곱근을 사용하는 방법

function solution (num) {
    if(!num || num === 1) return false;
    for (let i = 2; i <= Math.sqrt(num); i++) {
        if (num % i === 0) return false;
    }

    return true;
}

Math.sqrt () 함수를 써서 제곱근을 활용한다.

num 의 제곱근보다 작은 수들을 다 돌려봐서 전부 나누어지지 않는다면,

제곱근보다 큰 수에서도 계속 나눠지는 수가 나올 수 없다. 

그래서 제곱근까지만 반복문을 돌려도 판별이 가능하다.