素数，又称质数，是指除 1和其自身之外，没有其他约数的正整数。例如 2、3、5、13 都是质 数，而 4、9、12、18 则不是。 虽然素数不能分解成除 1和其自身之外整数的乘积，但却可以分解成更多素数的和。你需要编程 求出一个正整数最多能分解成多少个互不相同的素数的和。 例如，21 = 2 + 19 是 21的合法分解方法。21 = 2 + 3 + 5 + 11 则是分解为最多素数的方法。
输入 n (10 ≤ n ≤ 200)。
输出 n 最多能分解成多少个不同的素数的和。
输入 输出:
样例1, 21 4
样例2, 128 9
这是我的方法
<code class="hljs cpp has-numbering"><span class="hljs-preprocessor">#include<iostream></span></code>
#include<cmath>
using namespace std;
int num[50];
int n;
int index=0;
int maxtotal=-1;
bool issu(int m)//判断素数
{
if (m==2)
return true;
else if (m%2==0)
return false;
else
{
int k=sqrt(m)+1;
for (int i=2;i<=k;i++)
{
if (m%i==0)
return false;
}
}
return true;
}
void fun(int k,int sum,int total)//k为当前下标，sum为总和，total为使用的数字的个数
{
if (sum==n)
{
if (total>maxtotal)//更新total
{
maxtotal=total;
}
return ;
}
if (sum>n||k>=index)//如果sum超过n，或者下标大于素数个数结束
{
return ;
}
fun(k+1,sum+num[k],total+1);
fun(k+1,sum,total);
}
int main()
{
cin>>n;
for (int i=2;i<=n;i++)
{
if (issu(i))//如果是素数，将其存进num数组
{
num[index++]=i;
}
}
fun(0,0,0);
cout<<maxtotal;
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
但我老师给出了更牛逼的做法。我老师的做法,利用哥德巴赫猜想。
<code class="hljs cpp has-numbering"><span class="hljs-preprocessor">#include<iostream></span></code>
#include<cmath>
using namespace std;
int num[50];
int n;
int index=0;
bool issu(int m)//判断素数
{
if (m==2)
return true;
else if (m%2==0)
return false;
else
{
int k=sqrt(m)+1;
for (int i=2;i<=k;i++)
{
if (m%i==0)
return false;
}
}
return true;
}
int main()
{
cin>>n;
int sum=01,i,j;
for (int i=2;i<=200;i++)
{
if (issu(i))//如果是素数，将其存进num数组
{
num[index++]=i;
}
}
//_______________________________
for ( i=0;sum<n;i++)//将素数逐个累加
sum+=num[i];
if (sum==n)//如果正好等于n，即为正解
{
cout<<i;
return 0;
}
for ( j=2,sum-=n;j<=sqrt(sum);j++)//当sum>n时，需要sum-=n，
{
if (sum%j==0)
break;
}
//此时sum不是质数就是合数
if (j>sqrt(sum))//如果是质数将个数减1
i–;
else//如果是合数，则减2
i-=2;
cout<<i;
return 0;
}