分解质因式
数学定理:根据算术基本定理,不考虑排列顺序的情况下,每个正整数都能够以唯一的方式表示成它的质因数的乘积。
即:任何一个数都可以写成 $$N = P_{p1}^{a1} + P_{p2}^{a2} + \ldots + p_{pk}^{ak} $$ 其中P为质数
故我们引伸出分解质因数的算法:
原理:我们从第一个质因数开始枚举到\(\sqrt{n}\) 如果其能整除,则说明它是n的一个质数。
但,也许有些人会疑惑它这样子枚举不是会枚举到合数吗?
确实,他会枚举到合数,但是这些合数在我们分解质因数的途中也被分解掉了,故而枚举不到这些合数。
即:设我们分解一个质因数\(N\)则我们会从2开始分解它
我们会尝试它能不能被\(P_1\)分解,则被2分解,如果可以,我们就执行\(N = N / P_1\) 然后执行\(N = N / P_2\) , \(N = N / P_3\) \(\ldots\) \(N = N / P_k\) 在此途中,我们每枚举到\(P_i\)的时候,设从 \(2 \sim i-1\)此时有一个合数是\(N\)的约数,设其为\(d\)。但我们这个合数也可以被分解为 $$d = P_{p1}^{b1} + P_{p2}^{b2} + \ldots + p_{pi-1}^{bi-1} $$ 故而这个合数自然而然的在前面的枚举的过程中被分解掉了。
所以总结来说,既然\(2\sim i-1\)这个过程中所有合数都被分解之前的质因数除掉了,所以如果我们取到了新的可以整除\(N\)的数\(num\)的话,这个\(num\)只能是新出现的质因数\(P_i\) 了
代码:(yxc版本)
#include <iostream>
#include <algorithm>
using namespace std;
void divide(int x)
{
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
{
int s = 0;
while (x % i == 0) x /= i, s ++ ;
cout << i << ' ' << s << endl;
}
if (x > 1) cout << x << ' ' << 1 << endl;
cout << endl;
}
int main()
{
int n;
cin >> n;
while (n -- )
{
int x;
cin >> x;
divide(x);
}
return 0;
}
作者:yxc
链接:https://www.acwing.com/activity/content/code/content/49974/
来源:AcWing