소수 인지 판단

소수

약수가 1과 자기 자신 밖에 없는, 1보다 큰 자연수.

한편 1보다 큰 자연수 중 소수가 아닌 것은 합성수(composite number)라고 한다.

소수의 개수는 무한하며, 이는 유클리드의 정리에 의해 증명되었다.

 

N이 소수가 되려면, 2보다 크거나 같고 N-1보다 작거나 같은 자연수로 나누어 떨어지면 그 값은 소수가 아니기 때문에 이 방법을 다음과 같은 코드작성 할수 있다. 

funtion isPrime(num)
{
  if( num  < 2 ) return false

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

그러나  이런 식으로 구현할시 복잡도는 O(n)이 된다 

이 복잡도를 줄이기 위해 방법을 고민하던 중 에라토스테네스의 체라는 것을 찾을 수 있었다.

 

https://hellowoori.tistory.com/36

 

소수(prime number)와 에라토스테네스의 체

 

너무 잘 설명해주셔서 나머지는 패스 ~

수학 공부를 더 해야 할것 같다...ㅠ