50ptsWA了

NEGATUIVE_SEVEN_DL @ 2024-08-07 10:48:27

#include<bits/stdc++.h>
using namespace std;
long long n;
long long zs(long long t)
{
    for(int i=2;i<=sqrt(t);i++)
    {
        if(t%i==0)
        {
            return 1;
        }
    }
    return 0;
}
int main()
{
    cin>>n;
    for(int i=2;i<=n;i++)
    {
        for(int j=i;j<=n;j++)
        {
            if(zs(i)==0&&zs(j)==0&&zs(n-i-j)==0)
            {
                cout<<i<<' '<<j<<' '<<n-i-j;
                return 0;
            }
        }
    }
    return 0;
}

by humingming @ 2024-08-07 21:27:16

你这里如果直接写暴力它的复杂度是O（n^3）,它的数据给到20000会爆，可以先特判偶数情况```cpp if(is_prime(n-4)) { cout<<"2 "<<"2 "<<n-4; return 0; }

然后再模拟，模拟的时候可以再特判偶数，减少复杂度```cpp
for (int i=3;i<n;i++)
    {
        if((i%2)!=0&&is_prime(i))
        for (int j=i;j<n;j++)
        if((j%2)!=0&&is_prime(j))
        if(is_prime(n-i-j)) 
        {
            cout<<i<<" "<<j<<" "<<n-i-j;
            return 0;
        }
    }

by daijinxiang @ 2024-08-08 12:21:13

@xxxxx_ 不要这么麻烦！
我的提交记录+AC记录

直接质数筛+暴力枚举！

My code:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define int long long
using namespace std;
const int N=1e5+5;
bool vis[N];
int n;
void check() {
    vis[0]=vis[1]=true;
    for(int i=2; i<=20005; i++) {
        if(!vis[i]) {
            for(int j=i*i; j<=20005; j+=i)
                vis[j]=true;
        }
    }
}
signed main() {
    check();
    cin>>n;
    for(int i=2; i<n; i++) {
        for(int j=i; j<n; j++) {
            for(int k=j; k<n; k++) {
                if(i+j+k!=n) continue;
                if(vis[i]) continue;
                if(vis[j]) continue;
                if(vis[k]) continue;
                cout<<i<<" "<<j<<" "<<k;
                return 0;
            }
        }
    }
    return 0;
}

by daijinxiang @ 2024-08-08 12:22:39

@xxxxx_ 回了就回复OK！！！

by NEGATUIVE_SEVEN_DL @ 2024-08-08 20:17:39

@daijinxiang ok谢谢！

by NEGATUIVE_SEVEN_DL @ 2024-08-08 20:18:02

@humingming 谢谢过了！

by jebfghbbcdsl @ 2024-09-16 21:40:12

用欧式筛做的，求关(QWQ)

#include<cstdio>
int n,cnt,prime[20010];
bool vis[20010];
void sieve(int n){
    vis[0]=vis[1]=1;
    for(int i=2;i<=n;i++){
        if(!vis[i])prime[++cnt]=i;
        for(int j=1;j<=cnt&&i*prime[j]<=n;j++){
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)break;
        }
    }
}
bool is_prime(int x){
    if(x<2)return 0;
    for(int i=2;i*i<=x;i++)
        if(x%i==0)return 0;
    return 1;
}
int main(){
    scanf("%d",&n);sieve(n);
    for(int i=1;i<=cnt;i++)
        for(int j=i;j<=cnt;j++){
            int k=n-prime[i]-prime[j];
            if(is_prime(k)){
                printf("%d %d %d",prime[i],prime[j],k);
                return 0;
            }
        }
    return 0;
}