C++での複数のクエリにSieveO（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