分解质因数
题目 分解质因数
思路分析
什么是分解质因数：
每个合数都可以写成几个质数相乘的形式 其中每个质数都是这个合数的因数 把一个合数用质因数相乘的形式表示出来 叫做分解质因数 也叫做分解质因子 如30=2×3×5 分解质因数只针对合数
根据算术基本定理
不考虑排列顺序的情况下 每个正整数都能够以唯一的方式表示成它的质因数的乘积 n=p1^a1 * p2^a2 * p3^a3…..pn^an
比如一个数16 在分解时先找到2这个质因子，然后由于16/2后还可以/2，所以会在2这个质因子上产生次方 不优化版本：从2~n 找到能整除的因子然后算次方
这里有个性质
x 的质因子最多只包含一个大于 根号x 的质数。如果有两个，这两个因子的乘积就会大于 x，矛盾。
i 从 2 遍历到 根号x。 用 x / i，如果余数为 0，则 i 是一个质因子。
s 表示质因子 i 的指数，x /= i 为 0，则 s++， x = x / i 。
最后检查是否有大于 根号x 的质因子，如果有，输出。
质因数的底数和指数： 底数指质数的基数 比如在分解12=223中 2和3就是底数 而指数是指底数出现的次数 2出现了两次 所以指数是2
代码实现
#include<bits/stdc++.h>
using namespace std;
void divide(int x)
{
for (int i = 2; i <= x / i; i ++ ){//i <= x / i:防止越界，速度快于 i < sqrt(x)
if (x % i == 0){//i为底数
int s = 0;//s为指数
while (x % i == 0)
x /= i, s ++ ;
cout << i << ' ' << s << endl;//输出
}
}
if (x > 1)
cout << x << ' ' << 1 << endl;//如果x还有剩余，单独处理
cout << endl;
}
int main()
{
int n;
cin >> n;
while (n -- )
{
int x;
cin >> x;
divide(x);
}
return 0;
}
💬 评论