我们可以通过递归的方法来解决这个问题,一共有两种递归思路:
-
递归参数设置为起始值,然后累加:
1595486917937.jpg
原理如此,实现起来也很简单: image.png -
实际使用中通常使用第二种递归方式:
image.png
在递归过程中迭代从2开始的每个整数,如果是因子,则输出(不需要额外去判断是否是质数,因为递归的终止条件是当前数小于2,表示已经没有任何因子了--> 其因子必为质数(不存在任何其他因子)),并且递归处理,这样,对于每个需要处理的元素,都会从2开始循环寻找它的最小因子(需要注意的是,需要迭代所有小于n的整数,而不仅仅迭代到sqrt(n),因为我们要输出的是其所有质因子,当然也需要输出后半段)
源码:
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
void get_prim_factors(int n) {
if (n < 2) {
return;
}
for (int i = 2; i <= n; i++) {
if (n % i == 0) {
printf("%d ", i);
get_prim_factors(n / i);
return;
}
}
}
void get_prim_factors_2(int n, int x) {
if (n < 2) return;
if (n % x == 0) {
printf("%d ", x);
get_prim_factors_2(n / x, x);
}
else {
get_prim_factors_2(n, x + 1);
}
}
void solve(int n) {
get_prim_factors(n);
// get_prim_factors_2(n, 2);
}
int main(int argc, char const *argv[])
{
int n;
scanf("%d", &n);
solve(n);
return 0;
}
网友评论