소수 구하기

오늘은 조건문, 반복문 문제를 푸는게 대부분이라 문제를 풀다가 어려웠던 부분에 대해서 정리한다.

소수(Prime)

• 정의 : 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수

• 소수를 판별할 수 있는 방법

  1. 1과 자기 자신 사이의 모든 정수 확인하는 방법

     function isPrime(n) {
       for (let i = 2; i < n; i++) {
         if (n % i === 0) {
         return false;
         }
       }
       // 2가 주어진다 해도 i < n 에서 걸러져 바로 true가 반환 
       return true;
     }

  2. 제곱근을 사용해 배수들을 미리 거르는 방법

     • 64를 예로 들면 64의 제곱근은 √64(8) 즉, i가 8일때 나머지가 0이므로 소수가 아님을 판별할 수 있다.

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

  3. 에라토스테네스의 체

     • 에라토스테네스의 체는 간단히 말하자면, 1보다 큰 자연수 부터 n이하의 수를 배열에 담은 후 제곱근이 있는 수를 지우면, 남은 수가 소수가 된다는 의미이다.

     • 논리 연산자 not ! 을 사용해 소수이외에 수를 배열에 모으고 찾는 수가 그 안에 없으면 소수임을 반환할수도 있다.

     function isPrime(n) {
       let primes = [];
       const sqrt = Math.sqrt(n)
       for (let i = 2; i <= sqrt; i++) {
         if (primes[n]) {
           break;
         } else if (primes[i]) {
           continue;
         }
           for (let j = i ** 2; j <= n; j += i) {
           primes[j] = true;
         }
        }
       return !primes[n];
     }