数学知识——分解质因数

分解质因数模板

时间复杂度$O(\sqrt{n})$
把一个数$n$分解质因数之后，大于$\sqrt{n}$的质因数最多有一个，也正因此我们可以只考虑$\le \sqrt{n}$的数，最后再做特判。

void divide(int n)
{int x = sqrt(n);for (int i = 2; i <= x; i ++ ){int s = 0;while (n % i == 0){n /= i;s += 1;}if (s) printf("%d %d\n", i, s);}if (n > 1) printf("%d %d\n", n, 1);puts("");return ;
}

阶乘分解

给定整数 $N$，试把阶乘 $N!$ 分解质因数，按照算术基本定理的形式输出分解结果中的 $pi$ 和 $ci$ 即可。

输入格式
一个整数 $N$。

输出格式

$N!$分解质因数后的结果，共若干行，每行一对 $p_i,c_i$，表示含有 $p_i^{c_i}$
项。按照 pi 从小到大的顺序输出。

数据范围
$3\le N\le 10^6$

输入样例：

5

输出样例：

2 3
3 1
5 1

样例解释
$5!=120=23\ast 3\ast 5$

一个直观的想法是对于$1～N$内的每一个数分解质因数，再把对应质因数的次方数加起来就是$N!$分解质因数的结果。但是时间复杂度为$O(N\sqrt{N})$会超时。

考虑先预处理出$N$范围内的质数，对于每一个质数$p$，在$N!$分解质因数的结果中所对应的次方数为$\lfloor \frac{N}{p}\rfloor +\lfloor \frac{N}{p^2}\rfloor +\lfloor \frac{N}{p^3}\rfloor +...$。因为$N$以内素数个数大概为$N/lnN$,所以时间复杂度为$O(N/lnN\ast lo{g}_p^N)\approx O(N)$。

#include <iostream>
using namespace std;
#define N 1000010
bool st[N];
int prime[N];
int n, cnt = 0;
typedef long long ll;
void init(int n)
{for (int i = 2; i <= n; i ++ ){if(!st[i]) prime[cnt ++ ] = i;for (int j = 0; prime[j] * i <= n; j ++ ){st[i * prime[j]] =true;if (i % prime[j] == 0)break;}}
}
int main()
{cin >> n;init(n);for (int i = 0; i < cnt; i ++ ){int p = prime[i];int s = 0;for (ll j = p; j <= n; j *= p)s += n / j;printf("%d %d\n", p, s);}return 0;
}