[JavaScript] 소수 판별식

소수(Prime Number)를 판별하는데 여러가지 방법이 있는데 오늘은 내가 알고리즘 공부를 하면서 직접 찾아본

세 가지 방법을 정리하려한다.

 

1) 직접 나누어서 계산하기

 

2) N/2 까지만 나누어서 계산하기

 

3) N의 제곱근 ( √ ) 까지만 나누어서 계산하기

 

이렇게 세 가지 방법이다.

 

먼저 첫번째는 가장 간단한 방법인거 같다.

 

2부터 소수를 판별할 수 있으니 2를 먼저 return 해주고 나머지는 반복문을 이용해 나눠지는 수가 있는지 계산해보고 나눠지만 false를 return 해주고 for문을 빠져나올때까지 나눠지는 수가 없다면 true를 리턴해준다. (이때의 시간복잡도는 O(N) 이다.)

 

 

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

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

 

다음은 두번째 방법이다. 이것도 첫번째 방법과 같지만 for문을 좀 더 적게 돌릴 수 있다. 

num의 약수는 num의 절반을 넘을 수 없기 때문이다. (시간복잡도는 O(N) 이다.)

 

 

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

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

 

다음은 마지막 방법이다. 사실 나는 마지막 방법을 적기위해서 오늘 글을 썼다. 알고리즘 문제를 푸는데 힌트에 Math.sqrt()함수를 이용하라고 했다. 제곱근을 구하는 이유가 궁금해 인터넷에서 제곱근을 이용한 소수 판별을 찾아보았다.

 

 

function isPrime(num) {
  
  if(num === 2) {
    return true;
  }
  
  for(let i = 2; i <= Math.floor(Math.sqrt(num)); i++){
    if(num % i === 0){
      // 한 번이라도 나누어 졌으니 소수가 아니므로 return false
      return false; 
    }
  }
  // 나눠진 수가 없다면 해당 수는 소수이므로 return true
  return true; 
}

제곱근을 이용해서 푸는 방법은 이러했다.. 굳이 num의 제곱근보다 큰 수까지 반복문을 돌릴 필요가 없다고 한다. 

num의 제곱근보다 작은 수에서 나눠지는 수가 안나온다면 num의 제곱근보다 큰 수에서도 나눠지는 수가 나올 수 없기 때문이다. 

(그래서 이때의 시간복잡도는 O(√ N) 로 가장 빠르다. )

 

이렇게 총 세가지 방법으로 문제를 풀어보았다.. 

 

이미 인터넷에 많이 있는 방법이지만 내가 잊지않으려고 정리해보았다.