分解质因数概念:来自百度百科
将一个正整数分解质因数。例如:输入90,打印出90=233*5。
程序分析:对n进行分解质因数,应先找到一个最小的质数k,然后按下述步骤完成:
(1)如果这个质数恰等于n,则说明分解质因数的过程已经结束,打印出即可。
(2)如果n>k,但n能被k整除,则应打印出k的值,并用n除以k的商作为新的正整数n,重复执行第一步。
(3)如果n不能被k整除,则用k+1作为k的值,重复执行第一步。
递归和非递归
不过递归会超时
;- 非递归参考
yxc
的代码
#include <iostream>
#include <map>
using namespace std;
const int N = 100 + 10;
int n;
map<int, int> mp;
// 递归写法,但是递归会tle。哭了,调了好久。
void seperate_factor1(int x, int k)
{
if (x == k)
{
mp[k] ++;
for (auto t = mp.begin(); t != mp.end(); t++) printf("%d %d\n", t->first, t->second);
puts("");
return;
}
if (x > k)
{
if (x % k == 0) mp[k] ++, seperate_factor(x / k, k);
else seperate_factor(x, k+1);
}
}
// 非递归写法,参考了一下yxc大大的代码
void seperate_factor2(int x)
{
for (int i = 2; i*i <= x; i++)
{
if (x % i == 0)
{
int s = 0;
while (x % i == 0) x = x / i, s += 1;
printf("%d %d\n", i, s);
}
}
if (x > 1) printf("%d 1\n", x);
puts("");
}
int main()
{
scanf("%d", &n);
while (n--)
{
int a;
mp.clear();
scanf("%d", &a);
seperate_factor2(a);
// seperate_factor1(a, 2);
}
return 0;
}