结果对的但是TLE了，咋让他停下来？

wang6w6 @ 2024-07-05 14:39:34

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n;
ll ans[4],k=0;
ll zs(ll m){
    for(ll i=2;i*i<=m;i++){
        if(m%i==0){
            return 0;
        }
    }
    return 1;
}
void dfs(ll t){
    ll p=0;
    if(t>3){
        for(ll i=1;i<=3;i++){
            p=p+ans[i];
        }
        if(p==n){
            cout<<ans[1]<<" "<<ans[2]<<" "<<ans[3]<<endl;
            k=1;
        }else{
            return ;
        }
    }
    for(ll i=2;i<=n;i++){
        if(zs(i)==1){
            ans[t]=i;
            dfs(t+1);
            if(k==1){
                return ;
            }else{
                ans[t]=0;
            }
        }
    }
}
int main(){
    cin>>n;
    dfs(1);
    return 0;
}

by wangjiawen @ 2024-07-05 14:48:00

卡常，比如说

if(i>=9800000) break; @wang6w6

by DFs_YYDS @ 2024-07-05 14:51:56

@wang6w6 你可以剪枝，如果前两个数确定了，那第三个数就不需要循环枚举，直接就能算出来。

但好像不是这里的问题，你找到答案后直接用 exit(0) 跳出所有递归才行

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n;
ll ans[4],k=0;
ll zs(ll m){
    for(ll i=2;i*i<=m;i++){
        if(m%i==0){
            return 0;
        }
    }
    return 1;
}
void dfs(ll t){
    ll p=0;
    if(t>3){
        for(ll i=1;i<=3;i++){
            p=p+ans[i];
        }
        if(p==n){
            cout<<ans[1]<<" "<<ans[2]<<" "<<ans[3]<<endl;
            exit(0);
        }else{
            return ;
        }
    }
    for(ll i=2;i<=n;i++){
        if(zs(i)==1){
            ans[t]=i;
            dfs(t+1);
            if(k==1){
                return ;
            }else{
                ans[t]=0;
            }
        }
    }
}
int main(){
    cin>>n;
    dfs(1);
    return 0;
}

你看看这样行不行

by wang6w6 @ 2024-07-05 15:56:47

@wangjiawen 感谢，已AC

by wang6w6 @ 2024-07-05 15:57:05

@DFs_YYDS 感谢，已AC