[자료구조_Number] 소수, 소인수분해

소수 판별

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

  // 2부터 n-1까지의 수로 나눈다
  for (let i = 2; i < n; i++) {
    if (n % i === 0) {
      return false;
    }
  }

  return true;
}

위의 코드의 시간복잡도는 O(N)이다. 하지만 소수 판별 시 기본적으로 2의 배수는 무시해도 되며 2,3을 제외한 모든 소수가 6k-1, 6k+1(k는 정수)의 형태인것을 알고나면 다음과 같이 개선을 더 할 수 있다.

5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47...

시간 복잡도 O(sqrt(N))

function isPrime(n) {
  // 1보다 작은 수와, 2,3의 예외 처리를 해준다.
  if (n <= 1) return false;
  if (n <= 3) return true;

  
  // 2와 3의 합성수인 경우를 처리 해준다.
  if (n % 2 === 0 || n % 3 === 0) return false;

  
  // 2,3의 합성수에 대한 예외처리를 했기때문에 
  // 5부터 시작해 n의 제곱근까지 
  // 6k-1, 6k+1 소수로 분해가 가능한지 검사하면 된다. ( i+=6 )
  // 소수로 나눠진다면 합성수이고, 나눠지지 않는다면 소수이다.
  for (let i = 5; i ** 2 <= n; i += 6) {
    if (n % i === 0 || n % (i + 2) === 0) {
      return false;
    }
  }

  return true;
}

합성수는 소수들의 합성으로 이루어져 있기 때문에 자연수에서 소수를 제외하면 모두 합성수이다.
그렇기 때문에 소수는 1과 자기자신밖에 나눠지지않고, 소수를 제외한 합성수는 소수로 분해가 가능하다. (이렇게 합성수를 소수로 분해하는것이 소인수분해이다)

---

소인수분해

시간 복잡도 O(sqrt(N))

function primeFactors(n) {
  const arr = [];
  // n이 2로 나눠질 수 있는 만큼 2를 배열에 추가하고 2로 나눠준다.
  while (n % 2 === 0) {
    arr.push(2);
    n = n / 2;
  }

  // 이 지점에서 n은 홀수임이 확실하다.
  // 따라서 수를 2씩 증가시키면서 확인할 수 있다. (i += 2)
  for (let i = 3; i ** 2 <= n; i += 2) {
    while (n % i === 0) {
      arr.push(i);
      n = n / i;
    }
  }

  // 위의 반복문에서 제곱근까지 확인했음에도 나눠떨어지는 수가 없다면 남은 값은 소수이다. 
  // 해당값을 배열에 추가해준다. (남은 값이 2보다 큰 소수인 경우만 처리)
  if (n > 2) {
    arr.push(n);
  }
  
  return console.log(arr);
}

primeFactors(10); // [2, 5]
primeFactors(2000334214140); // [ 2, 2, 3, 5, 193, 172740433 ]