Prime Number:: 소수 찾기 코드 javascript

1. 기본 접근 방식(Brute Force):

소수를 찾는 순진한 접근 방식은 2에서 대상 숫자까지 모든 숫자를 반복하고 각 숫자에 대해 1과 자기 자신 이외의 숫자로 나눌 수 있는지 확인하는 것입니다. 나눌 수 없으면 그 숫자는 소수입니다.

다음은 JavaScript의 예입니다.

javascriptCopy code
function isPrime(number) {
  if (number <= 1) return false;

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

function findPrimeNumbers(n) {
  const primeNumbers = [];
  for (let i = 2; i <= n; i++) {
    if (isPrime(i)) {
      primeNumbers.push(i);
    }
  }
  return primeNumbers;
}

console.log(findPrimeNumbers(50));

이 방법은 작동하지만 가능한 모든 약수를 확인하므로 더 큰 수에는 효율적이지 않습니다.

2. 개선된 접근 방식(최적화된 Brute Force):

기본 접근 방식을 개선하기 위해 숫자의 제곱근까지만 제수를 확인하여 isPrime 함수를 최적화할 수 있습니다. 제곱근까지 약수가 없으면 나머지 숫자에도 약수가 없습니다.

javascriptCopy code
function isPrime(number) {
  if (number <= 1) return false;

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

// The findPrimeNumbers function remains the same as in the basic approach.

이 최적화는 소수를 확인하는 데 필요한 반복 횟수를 크게 줄입니다.

3. 모범 사례(에라토스테네스의 체): Sieve of Eratosthenes

에라토스테네스의 체는 주어진 한계까지 모든 소수를 찾는 고대 알고리즘입니다. 2의 배수부터 시작하여 각 소수의 배수를 반복적으로 표시합니다.

JavaScript로 구현한 내용은 다음과 같습니다.

function findPrimeNumbers(n) {
  const isPrimeArray = new Array(n + 1).fill(true);
  isPrimeArray[0] = false;
  isPrimeArray[1] = false;

  const sqrtN = Math.sqrt(n);
  for (let i = 2; i <= sqrtN; i++) {
    if (isPrimeArray[i]) {
      for (let j = i * i; j <= n; j += i) {
        isPrimeArray[j] = false;
      }
    }
  }

  const primeNumbers = [];
  for (let i = 2; i <= n; i++) {
    if (isPrimeArray[i]) {
      primeNumbers.push(i);
    }
  }
  return primeNumbers;
}

console.log(findPrimeNumbers(50));

에라토스테네스의 체는 주어진 한계까지 소수를 찾는 가장 효율적인 방법 중 하나이며 지정된 범위에서 소수를 찾는 모범 사례로 간주됩니다.

숫자의 제곱근까지 약수를 확인하는 것이 소수인지 확인하는 데 충분한 이유

합성수(소수가 아닌) 가 있는 경우 두 개 이상의 더 작은 정수로 분해할 수 있습니다. 숫자 n이 합성수이면 두 요소 a와 b의 곱으로 쓸 수 있습니다.

n = a * b

이제 a와 b는 모두 n의 제곱근보다 클 수 없습니다. 둘 다 n의 제곱근보다 크면 그들의 곱은 n보다 클 것입니다. 이는 모순입니다.

a > sqrt(n) and b > sqrt(n) => a * b > n

따라서 인수 중 하나 이상('a' 또는 'b')은 'n'의 제곱근보다 작거나 같아야 합니다. 따라서 숫자의 약수를 확인할 때 해당 숫자의 제곱근까지만 확인하면 됩니다.

제곱근까지 약수가 없으면 그 수를 곱할 수 있는 약수 쌍(a 및 b)이 없음을 의미합니다. 따라서 숫자는 소수여야 합니다.

이 원칙을 통해 약수를 확인하는 데 필요한 반복 횟수를 줄임으로써 소수 확인 알고리즘을 최적화할 수 있으므로 코드의 효율성이 크게 향상됩니다.