因子分解(递归)

1.素分解式(简单版)

任务描述
编写函数，输出一个正整数的素数分解式。主函数的功能为输入若干正整数（大于1），输出每一个数的素分解式。素数分解式是指将整数写成若干素数(从小到大)乘积的形式。例如：

20=2*2*5
36=2*2*3*3
53=53

输入样例:

6 10 24 100 1000 1001 1002001

输出样例：

6=2*3
10=2*5
24=2*2*2*3
100=2*2*5*5
1000=2*2*2*5*5*5
1001=7*11*13
1002001=7*7*11*11*13*13

解题思路：

从小到大遍历因子，只需找到一组因子对，然后递归分解这组因子对直到最小素数就行

参考代码：

#include<stdio.h>
void isprime(int a)
{for(int i=2;i*i<=a;i++){if(a%i==0){isprime(i);//递归分解因子printf("*");isprime(a/i);return;}}printf("%d",a);
}
int main()
{int a;while(~scanf("%d",&a)){printf("%d=",a);isprime(a);printf("\n");}return 0;
}

2.素分解式(进阶版)

任务描述
编写函数，输出一个正整数的升级版素数分解式。主函数的功能为输入若干正整数（大于1），输出每一个数的升级版素数分解式。素数分解式是指将整数写成若干素数(从小到大)乘积的形式。升级版素数分解式是指将整数写成若干素数(从小到大)乘积的形式，每个素数只输出1次，后面加上其乘方（1次方省略不输出），具体格式见输出样例。

输入样例:

1000 1001 1002 1003 1004 1005 1006 1007 1008

输出样例:

1000=2^3*5^3
1001=7*11*13
1002=2*3*167
1003=17*59
1004=2^2*251
1005=3*5*67
1006=2*503
1007=19*53
1008=2^4*3^2*7

解题思路：

与上一题相比也就是加上了需要以指数的形式表示，就需要设一个变量去计数

参考代码：

这是第一版，写的有些乱，但思路很好理解：

#include<stdio.h>
#include<stdbool.h>
bool isprime(int a)//判断质数，是否最简
{if(a==1)return false;if(a==2)return true;for(int i=2;i*i<=a;i++){if(a%i==0)return false;}return true;
}
void solve(int n)
{int a=2,t=0;//t用于控制输出乘号，a是被遍历的可能的因子if(isprime(n))//如果本身就为素数就不必再找因子了{printf("%d",n);return;}while(n>1){int count=0;//统计该因子幂次while(n%a==0){n/=a;count++;}if(count)//若count不为0，也就是a为因子时{if(t)//如果不是第一个因子输出，控制输出格式的printf("*");t++;printf("%d",a);//输出因子if(count>1)//若幂次大于1，输出幂次printf("^%d",count);}do{a++;}while(!isprime(a)&&a<=n);//a往后推至下一个素数，且a不能大于要被分解的nif(a>n)//a大于n了就跳出循环break;if(isprime(n))//剩下的n为质数也跳出break;}if(n!=1)//此时剩下的n必定为最简因子printf("*%d",n);
}
int main()
{int n;while(~scanf("%d",&n)){printf("%d=",n);solve(n);printf("\n");}return 0;
}

优化版：

#include<stdio.h>// 递归函数，用于分解质因数并显示指数
void isprime(int a, int count) {for (int i = 2; i * i <= a; i++) {if (a % i == 0) {// 统计当前质因数的幂次int exponent = 0;while (a % i == 0) {a /= i;exponent++;}// 递归处理剩余部分if (count == 0) {//count等于0，说明为第一个因子printf("%d", i);} else {printf("*%d", i);}if (exponent > 1) {printf("^%d", exponent);}// 继续分解剩余部分isprime(a, 1);return;}}// 如果 a 是质数，直接输出if (a > 1) {if (count == 0) {printf("%d", a);} else {printf("*%d", a);}}
}int main() {int a;while (~scanf("%d", &a)) {printf("%d=", a);isprime(a, 0);  // 调用递归函数进行质因数分解printf("\n");}return 0;
}

3.最大质因子序列

题目描述
任意输入两个正整数m, n (1 < m < n <= 5000)，依次输出m到n之间每个数的最大质因子（包括m和n；如果某个数本身是质数，则输出这个数自身）。

输入格式

一行，包含两个正整数m和n，其间以单个空格间隔。

输出格式

一行，每个整数的最大质因子，以逗号间隔。

样例输入

5 10

样例输出

5,3,7,2,3,5

解题思路：

遍历每一个数，判断其中的因子比较得出最大质因子，思路很简单

参考代码：

初版：

#include<iostream>
using namespace std;
bool isprime(int x)//判断是否为素数因子
{if(x<=1)return false;if(x==2)return true;for(int i=2;i*i<=x;i++){if(x%i==0)return false;}return true;
}
int isrpime(int x)//判断因子并比较出最大因子
{int max=0;for(int i=2;i*i<=x;i++){if(x%i==0){if(isprime(i))max=max<i?i:max;if(isprime(x/i))max=max<(x/i)?(x/i):max;}}return max;
}
void solve(int m,int n)
{int t=0,x=0;for(int i=m;i<=n;i++){if(isprime(i))//如果遍历到的数本身就为素数，则直接输出{if(t)cout<<',';t++;cout<<i;}else//若不为素数，则从因子中寻找{x=isrpime(i);if(t)cout<<',';t++;cout<<x;}}
}
int main()
{int m,n;cin>>m>>n;solve(m,n);return 0;
}

用递归美化版：

#include <iostream>
using namespace std;// 判断一个数是否为质数
bool isprime(int x) {if (x <= 1) return false;if (x == 2) return true;for (int i = 2; i * i <= x; i++) {if (x % i == 0) return false;}return true;
}// 递归函数：找到一个数的最大质因数
int maxPrimeFactorRecursive(int n) {// 如果 n 是质数，直接返回 nif (isprime(n)) {return n;}// 从 2 开始逐个检查因数for (int i = 2; i * i <= n; i++) {if (n % i == 0) {// 找到一个因数 i，递归找到 n/i 的最大质因数int factor1 = i;int factor2 = n / i;// 递归找到 factor2 的最大质因数int maxFactor = maxPrimeFactorRecursive(factor2);// 返回较大的质因数return max(factor1, maxFactor);}}// 如果没有找到因数，返回 n（理论上不会执行到这里）return n;
}// 输出 m 到 n 之间的质数和非质数的最大质因数
void solve(int m, int n) {int t = 0;for (int i = m; i <= n; i++) {if (isprime(i)) {if (t) cout << ',';t++;cout << i;} else {int maxFactor = maxPrimeFactorRecursive(i);if (t) cout << ',';t++;cout << maxFactor;}}cout << endl;
}int main() {int m, n;cin >> m >> n;solve(m, n);return 0;
}

4.素因子去重

题目描述
给定一个正整数n，求一个正整数p，满足p仅包含n的所有素因子，且每个素因子的次数不大于1

输入格式

一个整数，表示n<=10^12

输出格式

输出一行，包含一个整数p。

样例输入

1000

样例输出

10

解题思路：

• 题目别理解错，p是去重后素因子得乘积
• 还有本题数据较大，需要开long long

参考代码：

1.借用set容器的去重特性，筛出质因子,这种可能有些耗内存。

#include<iostream>
#include<set>
#include<vector>
using namespace std;
typedef long long ll;
set<ll>ans;//注意为long long
// 判断一个数是否为质数
bool isprime(ll x) {if (x <= 1) return false;if (x == 2) return true;for (int i = 2; i * i <= x; i++) {if (x % i == 0) return false;}return true;
}
void solve(ll n)//将质因数存入set容器，借由其出重特性去重
{for(int i=2;i*i<=n;i++){if(n%i==0){if(isprime(i))ans.insert(i);if(isprime(n/i)){ans.insert(n/i);}elsesolve(n/i);return;}}ans.insert(n);
}
int main()
{ll n;cin>>n;solve(n);ll p=1;for(auto m:ans){p=p*m;}cout<<p;return 0;
}

2.用递归优化掉判断素数的函数：

#include<iostream>
#include<set>
using namespace std;
typedef long long ll;
set<ll>ans;
void solve(ll n)
{for(int i=2;i*i<=n;i++){if(n%i==0){solve(i);//如果i为素数则不会进入该if分支solve(n/i);//同理，用递归的方式分解为素因子return;}}ans.insert(n);//素因子会在递归在到达这一句
}
int main()
{ll n;cin>>n;solve(n);ll p=1;for(auto m:ans){p=p*m;}cout<<p;return 0;
}

3.不使用set容器

#include<iostream>
using namespace std;
typedef long long ll;
int main()
{ll n;ll m=1;cin>>n;//从2开始，逐个检查是否为n的因子//如果 i 是 n 的因数，那么 i 必然是一个质数，因为如果 i 是一个合数，它必然可以被更小的质数整除，而这些质数已经在之前的循环中被处理过了for(ll i=2;i<=n/i;i++){if(n%i==0){m*=i;while(n%i==0){//将n中所有i的因子去除n=n/i;}}}if(n>1){m*=n;}cout<<m<<endl;return 0;
}

练习题目：
1.在这个页面，第7.7关 函数的应用，任务07-07-05 素分解式，任务07-07-08 升级版素分解式

2.https://www.dotcpp.com/oj/problem2967.html

3.https://www.dotcpp.com/oj/problem2966.html

4.https://www.dotcpp.com/oj/problem2221.html