因子分解(递归)
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不能大于要被分解的n
if(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 是质数，直接返回 n
if (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);
}
else
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;
}
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