[javascript] 반복문을 이용한 소수 찾기 (에라토스테네스의 체)

11 Dec 2023

javascript

에라토스테네스의 체(Sieve of Eratosthenes)는 특정 범위 내에서 소수를 찾는 효율적인 알고리즘입니다. 이 알고리즘을 사용하여 자바스크립트를 통해 소수를 찾는 방법을 알아보겠습니다.

알고리즘 개요

에라토스테네스의 체 알고리즘의 기본 개념은 다음과 같습니다:

2부터 시작하여 모든 수를 소수라고 가정합니다.
가장 작은 소수(2)의 배수를 모두 제거합니다.
다음으로 남아있는 수를 찾아 반복하여 소수를 찾습니다.

자바스크립트 코드 예제

아래는 자바스크립트를 사용하여 에라토스테네스의 체 알고리즘을 구현한 코드 예제입니다:

function findPrimes(limit) {
  let primes = [];
  let isPrime = Array(limit + 1).fill(true);
  isPrime[0] = isPrime[1] = false;

  for (let i = 2; i <= Math.sqrt(limit); i++) {
    if (isPrime[i]) {
      for (let j = i * i; j <= limit; j += i) {
        isPrime[j] = false;
      }
    }
  }

  for (let i = 2; i <= limit; i++) {
    if (isPrime[i]) {
      primes.push(i);
    }
  }

  return primes;
}

const limit = 100;
const primeNumbers = findPrimes(limit);
console.log(primeNumbers); // [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

위 코드는 2부터 limit까지의 소수를 찾는 findPrimes 함수를 구현한 예제입니다. 이를 실행하면 해당 범위 내의 모든 소수가 반환됩니다.

에라토스테네스의 체 알고리즘은 소수를 빠르고 효율적으로 찾기 위한 유용한 방법이며, 자바스크립트를 비롯한 다양한 프로그래밍 언어에서 활용될 수 있습니다.

결론

자바스크립트를 사용하여 에라토스테네스의 체 알고리즘을 구현하여 소수를 효율적으로 찾는 방법에 대해 알아보았습니다. 이 알고리즘을 응용하여 다양한 수학적 문제나 프로그래밍 과제에 활용할 수 있습니다.