Prime Factorization using Sieve O(log n) for multiple queries
使用筛法在 O(logN) 的时间内查询多组数的素数因子
前言
通常, 我们使用 O(n ^ 2) 的两层循环来进行打表, 记录一个数字是否为素数, 再使用 O(n) 的循环来求所有素因子.
然而, Nitish Kumar提供了一种在 O(nloglogn) 内打表, O(logN) 时间内查询的算法.
核心思想
这种算法的核心思想是, 使用 spf[] 存放每一个数的最小素因子(Samllest Prime Factor), 对于每个数 /= 他的最小素因子, 直到这个数变为 1.
代码实现
#include "bits/stdc++.h"
using namespace std;
#define MAXN 100001
int spf[MAXN];
void sieve()
{
spf[1] = 1;
for (int i=2; i<MAXN; i++)
spf[i] = i;
// 排除所有偶数因子, 使计算量减半.
for (int i=4; i<MAXN; i+=2)
spf[i] = 2;
// 外层循环枚举 [3, sqrt(MAXN))
// 内层循环进行 [i * i, MAXN)的验证
// 有效地减少重复计算
for (int i=3; i*i<MAXN; i++){
if (spf[i] == i){
for (int j=i*i; j<MAXN; j+=i)
// 如果 spf[j] = j, 说明从未更新过值
// 更新过一次后不再更新, 保证spf[i]为 最小 素因子
if (spf[j]==j)
spf[j] = i;
}
}
}
vector<int> getFactorization(int x){
vector<int> ret;
while (x != 1){
ret.push_back(spf[x]);
x = x / spf[x];
}
return ret;
}
int main(int argc, char const *argv[])
{
sieve();
int x = 12246;
cout << "prime factorization for " << x << " : ";
vector <int> p = getFactorization(x);
for (int i=0; i<p.size(); i++)
cout << p[i] << " ";
cout << endl;
return 0;
}