[JavaScript] 소수 판별하기

소수(Prime Number)란 1과 자신으로밖에 나누어떨어지지 않는 숫자로 정의한다.
그러면 소수인지 아닌지 판별할 수 있는 함수 isPrime()를 만들어보자.
소수인지 판별하기 위해서는 다음과 같이 해야된다.

1. 결과변수를 result로 선언하고, 값을 false로 할당한다.
2. 나누어 떨어지는 횟수를 셀 변수를 count로 선언하고 0으로 초기화한다.
3. 1,3,5,...,숫자까지 나눠보고, 나누어 떨어지면 count를 올린다.
4. 만약 count가 3이면 반복문을 종료한다. 소수가 아니니까
5. 결과를 출력한다.

근데 자연수의 약수의 형태는 제곱근을 중심으로 좌우 대칭형이다.
16의 약수는 1,2,4,8,16이고, 20의 약수는 1,2,4,5,10,20이며, 소수인 13은 1,13이다. 각각 4, 4.xxx(20의 제곱근), 3.xxx(13의 제곱근)을 중심으로 대칭형이다. 따라서 처음부터 끝까지 나누는 것이 아니라 제곱근까지로 한정시켜버리면 계산 시간을 줄일 수 있다. 만약에 원하는 숫자가 1039061023046829302290229502781923461 따위의 매우 큰 숫자라면 엄청난 시간을 줄일 수 있는 것이다. 따라서 최종 알고리즘은 다음과 같다.

1. 결과변수를 result로 선언하고, 값을 false로 할당한다.
2. 나누어 떨어지는 횟수를 셀 변수를 count로 선언하고 0으로 초기화한다.
3. 1,3,5,...,숫자의 제곱근까지 나눠보고, 나누어 떨어지면 count를 올린다.
4. 만약 count가 2이면 반복문을 종료한다. 소수가 아니니까
5. count가 1이면 결과값에 true를 할당한다.
6. result를 출력한다.

위 알고리즘을 바탕으로 한 코드는 다음과 같다.

참고로 61은 전 야구선수 투머치토커(박찬호)의 등번호이며, 소수 맞습니다.