[javascript] 정수론 알고리즘

18 Dec 2023

javascript

정수론 알고리즘은 소수 판별, 최대공약수 계산, 모듈러 연산 등과 같은 정수에 대한 수학적 문제를 해결하는데 사용되는 알고리즘의 모음입니다.

소수 판별 알고리즘

소수 판별 알고리즘은 어떤 수가 소수인지 판별하는 알고리즘입니다. 대표적으로 에라토스테네스의 체 알고리즘이 있습니다. 에라토스테네스의 체는 2부터 시작하여 차례로 배수들을 지워가며 소수를 찾는 방법입니다.

function sieveOfEratosthenes(n) {
  let primes = [];
  let isPrime = new Array(n + 1).fill(true);
  isPrime[0] = isPrime[1] = false;
  for (let i = 2; i <= n; i++) {
    if (isPrime[i]) {
      primes.push(i);
      for (let j = i * i; j <= n; j += i) {
        isPrime[j] = false;
      }
    }
  }
  return primes;
}

console.log(sieveOfEratosthenes(20)); // Output: [2, 3, 5, 7, 11, 13, 17, 19]

최대공약수 계산 알고리즘

최대공약수는 두 개 이상의 정수의 공통된 약수 중 가장 큰 수를 의미합니다. 유클리드 호제법은 최대공약수를 구하는 알고리즘으로, 재귀적으로 구현할 수 있습니다.

function gcd(a, b) {
  if (b === 0) {
    return a;
  }
  return gcd(b, a % b);
}

console.log(gcd(24, 36)); // Output: 12

모듈러 연산

모듈러 연산은 어떤 수를 다른 수로 나눈 나머지를 구하는 연산입니다. 모듈러 연산은 원형 큐나 해싱 함수 등에서 자주 사용됩니다. 예를 들어, (a + b) % m은 두 수를 더한 뒤 모듈러 연산을 수행하는 것을 의미합니다.

function modulo(a, b) {
  return ((a % b) + b) % b;
}

console.log(modulo(-10, 3)); // Output: 2

정수론 알고리즘은 수학적인 개념을 기반으로 하며, 소수, 최대공약수, 모듈러 연산 등 다양한 분야에서 응용됩니다.

소수 판별 알고리즘

최대공약수 계산 알고리즘

모듈러 연산

참고 자료