2019-2020大中小学生联合训练赛第五场 F题 素数分解 【DFS】 【哥德巴赫猜想】

题目描述
素数，又称质数，是指除 1 和其自身之外，没有其他约数的正整数。例如 2、3、5、13 都是合 数，而 4、9、12、18 则不是。
虽然素数不能分解成除 1 和其自身之外整数的乘积，但却可以分解成更多素数的和。
你需要编程 求出一个正整数最多能分解成多少个互不相同的素数的和。
例如，21 = 2 + 19是21的合法分解方法。21 = 2 + 3 + 5 + 11则是分解为最多素数的方法。
输入
一个整数n(10≤n≤200)。
输出
n最多能分解成多少个不同的素数的和。
样例输入 Copy
21
样例输出 Copy
4

题目分析

首先是DFS解法，因为数据范围比较小，我们可以先把素数存在一个数组中，
对于当前的素数我们可以选择加或者不加，

#include<bits/stdc++.h>
using namespace std;
int count,su[250],n,Max;
int prime(int a) {
    for(int i=2; i*i<=a; i++)
        if(a%i==0)
            return 0;
    return 1;
}
void dfs(int t,int count,int num) {
    if(t==n) {
        Max=max(Max,count);
        return ;
    }
    if(  su[num]>n ||  t>n)  return ;       //避免死循环 
    dfs(t+su[num],count+1,num+1);
    dfs(t,count,num+1);
}
int main() {
    int  k=0;
    for(int  i=2; i<=250; i++)
        if(prime(i))     //存素数 
            su[k++]=i; 
    cin >> n ;

    dfs(0,0,0);
    printf("%d",Max);
    return 0;
}

二

利用哥德巴赫猜想

对于大于6的合数可以分解为两个素数的和。
我们可以从素数数组中从小往大依次加，用sum记录和，用J记录个数，直到sum加出N的范围时
终止程序，
此时超出范围的数为 sum-n；
也就是说我们要从之前的数中剔除sum-n；
n=sum-（sum-n），
才能满足和为n的条件。
因为加的过程中是从小到大依次往上加的，
1.如果sum-n是合数，必定能用前J个数中的两个素数组合出sum-n；输出J-2；
2如果sum-n是素数。那么前J个数中必定出现过这个素数，剔除掉即可，输出J-1
3如果递加的过程中sum==n，输出J 即为正解

#include<bits/stdc++.h>
using namespace std;
int prime(int a)
{
    for(int i=2;i*i<=a;i++)
    if(a%i==0)
    return 0;
    return 1;
}
int main() {
int  su[202],k=0,sum=0,j;
for(int  i=2;i<=250;i++)
if(prime(i))
su[k++]=i;
int n;  cin >> n ;
for( j=0;sum<n;j++)
sum=sum+su[j];
if(sum==n)
{
    printf("%d",j);
    return 0;
}

sum=sum-n;
if(prime(sum))
j=j-1;
else
j=j-2;
printf("%d",j); 



    return 0;
}