使用筛法O(log n)进行多次查询的C++素数分解

在这个问题中，我们需要创建一个程序来计算 *使用筛法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

sudhir sharma

更新于：2021年1月27日

2K+ 次浏览

启动你的职业生涯

通过完成课程获得认证

开始学习