에라토스테네스의 체

N보다 작은 소수들을 구하는 데 사용되는 알고리즘입니다.

에라토스테네스의 체의 구현은 아래 단계들을 거쳐 구현합니다.

N + 1 크기를 가지는 배열(sieve)을 준비하고, -1로 초기화합니다.
for문으로 2부터 N까지 순회하며, sieve[i]가 -1인 i를 찾습니다.
조건을 만족하는 i를 찾으면, N보다 작은 i의 배수들 j에 대해서 sieve[j]에 i를 넣어줍니다.
위 순회과정에서 sieve[i]에 -1이 저장되어 있던 수들이 소수입니다.

C++ 코드로 구현된 예시는 아래와 같습니다.

#include <bits/stdc++.h>
#define INF 999999999999
typedef long long ll;
using namespace std;

ll sieve[10001000];

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  sieve[1] = -1;
  for(ll i = 2; i <= 10000000; i++) {
    if(sieve[i] == 0) {
      sieve[i] = -1;
      for(ll j = i * 2; j <= 10000000; j += i) {
        sieve[j] = i;
      }
    }
  }

  return 0;
}

소인수분해

위 과정을 통해 N보다 작은 소수를 모두 구했다면, N보다 작은 수 Q에 대해 $O(log{Q})$ 시간 안에 소인수 분해가 가능합니다.

위에서 구현한 방식에서는 sieve[i]에는 i를 나눌 수 있는 소수가 저장되어 있기 때문에, 더 이상 나눌 수 없는 소수가 나올 때 까지, i를 sieve[i]의 값으로 나눠주면 i의 소인수분해가 가능합니다.

아래는 $10^7$ 이하의 수 Q를 입력받고, Q에 대한 소인수분해를 진행하여 소인수들을 primes 배열에 저장하는 코드입니다.

#include <bits/stdc++.h>
#define INF 999999999999
typedef long long ll;
using namespace std;

ll sieve[10001000];
ll Q;
vector<ll> primes;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  sieve[1] = -1;
  for(ll i = 2; i <= 10000000; i++) {
    if(sieve[i] == 0) {
      sieve[i] = -1;
      for(ll j = i * 2; j <= 10000000; j += i) {
        sieve[j] = i;
      }
    }
  }

  cin >> Q;
  while(sieve[Q] != -1){
    primes.push_back(sieve[Q]);
    Q /= sieve[Q];
  }
  if(Q > 1) primes.push_back(Q);

  return 0;
}