整数因子分解问题，为什么递归用错了，求牛人帮忙，先谢谢了

发布网友发布时间：2023-10-10 18:28

共3个回答

热心网友时间：2024-11-23 12:05

这个用递归式没有错，需要判断这个因子是否为素数，是素数，就是这个因子就只能出现一次，不是素数，继续分解
分解用for循环游历2~n-1

int sushu(int n)
{} //这个不写了，网上很多代码，是素数返回0.不是素数返回1，我直接调用

int q(int n)
{
int i,s;
if(sushu(n))
s=0;
else
{
for(i=2;i<n;i++)
if(n%i==0)
{
s+=1;
s+=q(i);
}
}
return s;
}追问额，能详细一点吗？谢谢

追答意思就是这个因子是素数了，就不用再分解了
不是素数，就再分解，同时可能加上1

热心网友时间：2024-11-23 12:06

int q(int n){

int result = 1;
int i = n - 1;
for(i = n - 1; i > 1; i-- )
{
if(n % i == 0 )
{
result += q(n / i);
}
}
return result;

}

热心网友时间：2024-11-23 12:06

#include<stdio.h>
main()
{
int n;
int q(int n);
while(scanf("%d",&n)!=EOF){
printf("%d\n",q(n));
}
return 0;
}
int q(int n){

int i,result=1;
if(n==1)
return result;
else if(n==2)
return result;
else if(n==3)
return result;
else if(n>3)
for(i=n-1;i>1;i--)
if(n%i==0)
result=result+q(i);
return result;
}追问额，答案对了，但提交却是超时，求大牛指点

追答你把递归的方法改为非递归的方式试试，反正递归调用的确是耗时。我先想想。。
我用C++写的，不知道能不能过：
#include
#include
using namespace std;
int main()
{
int i,n,count,current_position;
vectorob;
while(cin>>n)
{
ob.clear();
count=1;
current_position=0;
ob.push_back(n);
ob.push_back(-1);
while(current_position>-1&&ob[current_position]!=-1)
{
n=ob[current_position];
for(i=n/2;i>1;i--)
if(!(n%i))
{
count++;
ob[current_position]=n/i;
ob.push_back(-1);
current_position++;
}
current_position--;
}
cout<<count<<endl;
}
return 0;
}