[알고리즘]소수

소수 판별법

1. O(n): 1~n-1까지 전부 나눠보고 나눠지지 않는 것을 확인한다.

bool isPrime(int n) {
  if (n == 1) return false;
  for (int i = 2; i < n; i++)
    if (n % i == 0) return false;
  return true;
}

2. O(n^(1/2)): 1~n^(1/2)까지 전부 나눠보고 나눠지지 않는 것을 확인한다.

bool isPrime(int n) {
  if (n == 1) return false;
  for (int i = 2; i * i <= n; i++)
    if (n % i == 0) return false;
  return true;
}

에라토스테네스의 체

2부터 배수를 전부 지운다. 단, 현재 숫자가 n이라고 n+1부터 확인할 필요가 없다. n 미만의 숫자로 나눌 수 있는 것은 이미 다 지워졌으므로 n^2부터 시작하면 된다. 시간복잡도: O(n lg lg n)

vector<bool> isPrime(limit+1, 1);
isPrime[1] = false;
for (int i = 2; i * i <= limit, i++) {
  if (!isPrime[i]) continue;
  for (int j = i * i; j <= limit; j += i)
    isPrime[j] = false;
}

소인수분해

n을 소인수분해 할 때, i는 2부터 시작해서 나눌 수 있는 만큼 계속 나눈다. 더 이상 나눌 수 없을 때 i를 증가시킨다. 마지막으로 i가 n^(1/2)보다 크다면 n은 소수이므로 계산을 멈추고 n에 저장된 수를 소인수에 추가한다. 시간복잡도: O(n^(1/2))

void printPrimeFactors(int n) {
  for (int i = 2; i * i <= n; i++) {
    while (n % i == 0) {
      cout << i << ' ';
      n /= i;
    }
  }
  if (n != 1) cout << n;
}