C++에서 여러 쿼리에 대해 Sieve O(log n)를 사용한 소인수 분해

이 문제에서는 여러 쿼리에 대해 Sieve O(log n)를 사용하여 소인수분해를 계산하는 프로그램을 만들어야 합니다.

일반적인 방법은 O(sqrt(n) ) 시간이 걸리므로 여러 쿼리에서 필요한 시간이 엄청나게 늘어납니다.

먼저 요약하자면

소인수 분해 의 숫자에는 소인수만 포함되며 소인수의 곱은 포함되지 않습니다.

에라토스테네스의 체 주어진 범위 내에서 모든 소수를 생성하는 알고리즘입니다.

솔루션 접근 방식

문제의 해는 수를 나누는 가장 작은 인수를 찾아 인수로 저장하고 인수로 나누어 수를 갱신함으로써 구합니다. 이 과정은 나눗셈 후 숫자가 1이 될 때까지 재귀적으로 수행되므로 다른 요소가 불가능합니다.

계산은 에라토스테네스 체 를 사용하여 수행됩니다. 이는 가장 작은 소인수를 찾는 시간 복잡성을 줄입니다.

우리 솔루션의 작동을 설명하는 프로그램

예시

#include <iostream>
using namespace std;
int primes[100001];

void sieveOfEratosthenes(int N) {
   
   N+=2;
   primes[1] = 1;
   for (int i=2; i<N; i++)
      primes[i] = i;
   for (int i=4; i<N; i+=2)
      primes[i] = 2;
   for (int i=3; i*i<N; i++) {
      if (primes[i] == i) {
         for (int j=i*i; j<N; j+=i)
            if (primes[j]==j)
               primes[j] = i;
      }
   }
}
void findPrimeFactors(int num) {
   
   sieveOfEratosthenes(num);
   int factor;
   while (num != 1) {
      factor = primes[num];
      cout<<factor<<" ";
      num /= factor;
   }
}

int main() {
   int N = 45214;
   cout<<"Prime factorization of the number "<<N<<" using sieve is ";
   findPrimeFactors(N);
   return 0;
}

출력

Prime factorization of the number 45214 using sieve is 2 13 37 47