소수구하기

[shldhee]

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

소수

1과 자기 자신으로만 나누어 떨어지는 1보다 큰 양의 정수.
(1과 자기 자신으로만 떨어진다 = 약수가 두 개 뿐이다)

예) 19의 약수는 [1, 19] 이므로, 19는 소수이다.

약수

나눴을 때 나머지가 0이 되는 수.

예) 9의 약수는 [1, 3, 9] 이므로, 9는 소수가 아니다.

[shldhee]

예를 들어, num이 9일 경우 2부터 8까지 모든 수를 순회해야만 9가 소수인지 아닌지 판별되지만, 9를 3으로 나누어 0으로 떨어지는 시점에서 이미 소수가 아니라는 결론을 도출할 수 있다.

그렇다면 모든 수를 순회하지 않도록 과정을 최소화할 수 있는 방법은 없을까?

2부터 자신의 양의 제곱근 이하의 수까지 나누어 소수 여부를 판별할 수 있는 소수판별법을 사용하여 과정을 단축 시킬 수 있었다.

[shldhee]

https://sumin-k.medium.com/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-javascript-%EC%99%84%EC%A0%84-%ED%83%90%EC%83%89-%EC%86%8C%EC%88%98-%EC%B0%BE%EA%B8%B0-1fdcdca4f59b