c++用递归方法求1+2+3+...+n的和并将其中的素数去除后之和

Question

#include<stdio.h>
int n;
int sum1(int n)/*递归求1+2+....+n*/
{

if(n==0)return 0;
return n+sum1(n-1);
}
int insprime(int n)//判断是否是素数
{
if(n<=1)return false;
for(int i=2;i<n;i++)
if(!(n%i))return false;
return true;
}
int sum2()//求1到n素数和
{
int sum=0;
for(int i=1;i<=n;i++)
if(insprime(i))
sum+=i;
return sum;
}

void main()
{
printf("输入要求和的n\n");
scanf("%d",&n);
int k=sum1(n);
printf("所求和为:%d\n",k);
k=sum1(n)-sum2();
printf("1到n非素数和为:%d\n",k);
}
看看我的能不能再简单点？？？

Answer 1

#include <stdio.h>
bool prime(int n)
{
if (n==2)
{
return true;
}
if (n<2)
{
return false;
}
int temp = n/2;
bool flag = true;
for(int i=2; i<=temp; i++)
{
if (n%i==0)
{
flag = false;
break;
}
}
return flag;
}
void sum(int n,int &a,int &b)
{
if (n==0)
{
return;
}
else
{
a+=n;
sum(n-1,a,b);
if(!prime(n))
{
b+=n;
}
}
}
int main()
{
printf("Input a n:");
int data,a=0,b=0;
scanf("%d",&data);
sum(data,a,b);
printf("sum of 1-%d is %d,without prime numbei is %d\n",data,a,b);
return 0;
}

Answer 2

#include <iostream>
#include <MATH.H>
using namespace std;
int f(int n)//判断n是否为素数，是则返回1，否则返回0
{
int i=2;
while(i<=sqrt(n))
if (n%i++==0)return 0;
return 1;
}
long fun(int n)
{//递归求和
if(n==1)return 1;
return f(n)? fun(n-1):n+fun(n-1);//n为素数则不加在内
}
void main()
{
int n;
long sum;
cin>>n;
sum=fun(n);
cout<<"sum="<<sum<<endl;
}

追问

看看我前面的能不能简单点？

追答

在递归求前n项和的时候同时求其中的素数和，这样就无需另外再次求和，可提高效率
#include
int sum2=0;
int insprime(int n)//判断是否是素数
{
if(n<=1)return false;
for(int i=2;i<=n/2;i++)//测试i到n/2即可，减少运行时间
if(!(n%i))return false;
return true;
}
int sum1(int n)/*递归求1+2+....+n*/
{

if(n==1)return 1;//到1即可无需到0
if (insprime(n))sum2+=n;//求素数和
return n+sum1(n-1);
}
void main()
{
int n;
printf("输入要求和的n\n");
scanf("%d",&n);
int k=sum1(n);
printf("所求和为:%d\n",k);
k=k-sum2;
printf("1到%d非素数和为:%d\n",n,k);
}

Answer 3

#include <iostream>
using namespace std;
int f(int n)//判断n是否为素数，是则返回1，否则返回0
{
int i=2;
while(i<=n/2)
if (n%i++==0)
return 0;
return 1;
}
long fun(int n)
{
if(n==0)
return 0;
return f(n)? fun(n-1):n+fun(n-1);
}
long fun1(int n)
{
if(n==1)
return 1;
return n+fun1(n-1);

}
int main()
{
int n;
long sum,sum1;
cin>>n;
sum=fun1(n);
sum1=fun(n);
cout<<"未去掉素数的和："<<sum<<endl;
cout<<"去掉素数之后的和："<<sum1<<endl;
return 0;
}