数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学使用筛法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
更新于：2021年1月27日
2K+ 次浏览
广告