소수판별하기

이거 소수판별이라고면 치면 나오는 내용이긴한데

한번 정리해두면

안까먹을거 같아서 정리해보려한다.

 

어떤 숫자가 소수인지 아닌지 판별을 할때는

2부터 그 숫자-1까지 하나하나 나누면서 조져보는 방법과

 

2부터 그 숫자의 제곱근 까지 하나하나 나누면서 조지는 방법이 있다.

 

코드로 보면

function checkPrime(number) {
  if(number === 1)return false;
  if(number === 2)return true

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

number 가 1 인 경우는 바로 false를 리턴하고

이게 1부터 자기자신-1까지 하나하나 조져보는 방법이다.

 

소수는 1과 자기자신 말고는 나눠지는 숫자가 없어야 한다.

그니까 2부터 자기자신-1 까지의 숫자들로는 나눠지면 안된다.

여기서 나눠진다는거는 나머지가 0이라는 뜻이다

그러니 나머지가 0이면 바로 false 리턴해준다.

나눠지지 않는다면 true를 리턴한다.

 

이경우에는 O(N)의 시간복잡도를 갖게된다.

 

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

그리고 압도적으로 성능이 좋은 방법이 제곱근을 이용하는거다.

 

자연수 N이 소수이기 위한 조건은 N이 N의 제곱근보다 크지 않은 어떤 소수로도 나눠지지 않는다.

라는데 ㅎㅎㅎㅎㅎ

왜 그런지는 아무리 봐도 모르겠다.

문과인 나는 봐도 모르겠더라 그런거.

ㅎ그냥 외우기로 했다.

 

코드가 작동하는 원리는 위의 코드와 같다.

number가 1또는 2이면 얼리리턴 해주고,

아니면 for문 돌리는데 범위가 다르다.

위에서는 number-1까지 돌렸는데,

이번엔 number의 제곱근보다 크거나 같을 때 까지 돌린다.

그니까 number가 18이라 치면 number의 제곱근은 4.몇 이 될거다.

그니까 i 는 2부터 시작해서 4까지 커지면서 연산한다.

 

같은 원리를 이용해서 while문으로도 만들 수 있다.

function primeCheck(num) {
  if(number === 1) return false;
  if(number === 2) return true;
  
  let i = 2;
  while (i * i <= num) {
    if (num % i === 0) return false;
    i += 1;
  }
  return true;
}

이 코드가 압도적으로 성능이 좋은 이유는

범위가 number의 제곱근 까지 이기 때문에 O(√N)의 시간 복잡도를 갖게 된다.

예시로 들은 18의 경우위의 코드는 for문이 16번 돌아가고,

 아래의 코드는 3번만 돌아간다.

이게 숫자가 10000 이되고 1000000이 되면 그 차이가 어마어마하다.

그니까 아래의 코드를 잘 외워두고 사용하자.

이해를 한다면 좋겟지만 그건 나에게는 힘들지 않을까 싶다..ㅎ