소수 판별법 (javascript)

소수란?

소수는 1보다 큰 자연수 중, 1과 자기 자신만을 약수로 가지는 수이다.

소수 판별법

소수를 판별하는데에 있어서 여러가지 방법이 있다.

1. 직접 나눠서 계산
2. n / 2 까지 나눠서 계산
3. n의 제곱근 까지 나눠서 계산

위 3가지의 방법에 대해서 정리해보려 한다.

---

1. 직접 나눠서 계산

시간 복잡도 O(N)

2부터 소수를 판별할 수 있으니 2를 먼저 return 해주고,
나머지는 반복문을 돌면서 나눠지는 수가 있는지 확인하고
나눠지면 false를 return / 반복문이 종료될 때 까지 나눠지지 않았다면 true를 return

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

2. n / 2 까지 나눠서 계산

시간 복잡도 O(N)

첫번째 방법과 동일하지만 for문을 더 작게 돌릴 수 있다.
num의 약수는 num의 절반을 넘을 수 없기에, n / 2 만큼만 반복문을 돌린다.

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

3. n의 제곱근 까지 나눠서 계산

시간 복잡도 O(√ N) / 가장 빠른 방법

num의 약수는 쌍으로 존재한다. 곱해서 num이 되는 짝이 있다는 뜻이다.
아래의 그림처럼 쌍을 이루는 약수 중, 하나만 찾으면 나머지 하나는 찾지 않아도 된다.

ex) 8의 약수는 1, 2, 4, 8이다. 1과 8, 2와 4를 곱하면 8이 된다.
ex) 9의 약수는 1, 3, 9이다. 1과 9, 3과 3을 곱하면 9가 된다.

따라서 제곱근까지만 확인하여 반복 횟수를 많이 줄일 수 있다.

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