숫자 알고리즘

소수 테스트, 소인수 분해 알고리즘을 해보자.

---

소수 테스트

주어진 값이 소수인지 확인하는 알고리즘은 쉽게 작성 가능합니다.

const isPrime(n) {
  if (n <= 1) {
    return false
  }

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

  return true
}

하지만 다음 코드의 시간 복잡도는 O(n)입니다.

시간 복잡도를 줄이기 위해서 2의 배수를 무시하거나, 주어진 값의 제곱근까지만 확인하는 등 방법을 제시할 수 있습니다.

---

다른 방법

주어진 값의 제곱근까지만 확인하는 방법으로 작성해보겠습니다.

const isPrime = (n) => {
  if (n <= 1) {
    return false;
  }

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

  return true;
};

시간 복잡도가 O(sqrt(n))으로 줄어듭니다.

---

소인수분해

const primeFactors = (n) => {
  while (n % 2 == 0) {
    console.log(2);

    n = n / 2;
  }

  for (let i = 3; i * i <= n; i += 2) {
    while (n % i == 0) {
      console.log(i);

      n = n / i;
    }
  }

  if (n > 2) {
    console.log(n);
  }
};

시간 복잡도 : O(sqrt(n))

---

못생긴 숫자

소인수가 2, 3, 5 로 이루어진 숫자를 못생긴 숫자라고 정의할 때, 1부터 주어진 숫자까지의 못생긴 숫자들을 출력해보자.

먼저 숫자를 2, 3, 5로 나누어지지 않을 때까지 나눕니다.

그 후 나누어진 숫자가 1이라면 못생긴 숫자입니다.

const maxDivide = (n, divisor) => {
  while (n % divisor == 0) {
    n /= divisor;
  }

  return n;
};

const isUglyNum = (n) => {
  n = maxDivide(n, 2);
  n = maxDivide(n, 3);
  n = maxDivide(n, 5);

  return n === 1;
};

1부터 n까지 반복해봅시다.

const arrayUglyNum = (n) => {
  let uglyNums = [];

  for(let i = 1, i < n; i++) {
    if (isUglyNum) {
      uglyNums.push(i)
    }
  }

  return uglyNums;
}

maxDivide의 시간 복잡도 : n과 divisor에 따라 달라지는 로그 함수

arrayUglyNum의 시간 복잡도 : maxdivide의 시간 복잡도 * n