40分蒟蒻求助

wshiren @ 2022-08-10 20:42:27

#include <bits/stdc++.h>
using namespace std;

bool isPrime(int num){
    if(num < 2){
        return false;
    }
    for(int i = 2; i < sqrt(num); ++i){
        if(num % i == 0) return false;
    }
    return true;
}

int main(){
    int n;
    cin >> n;
    bool flag = false;
    for(int i = 2; i < n; ++i){
        for(int j = 2; j < n; ++j){
            for(int k = 2; k < n; ++k){
                if(isPrime(i) && isPrime(j) && isPrime(k) && i + j + k == n){
                    cout << i << ' ' << j << ' ' << k << ' ' << endl;
                    return 0;
                }
            }
        }
    }
}

by IamZZ @ 2022-08-10 20:50:20

@wshiren

时间复杂度太大了……

先把n以内的质数全部筛出来，再用暴力求答案

by _sin_ @ 2022-08-10 20:57:02

枚举前两个数，计算出第三个数，判断第三个数是否是质数

by WZWZWZWY @ 2022-08-10 21:02:05

蒟蒻路过此地，帮您加速代码 @wshiren

#include <bits/stdc++.h>
using namespace std;

bool isPrime(int num){
    for(int i = 2; i <= sqrt(num); ++i){
        if(num % i == 0) return false;
    }
    return true;
}

int main(){
    int n;
    cin >> n;
    bool flag = false;
    for(int i = 2; i < sqrt(n); ++i){
        for(int j = 2; j < sqrt(n); ++j){
                int k = n - i - j; //这里不需要循环，直接减，i,j,k的和就是n了
                if(isPrime(i) && isPrime(j) && isPrime(k)){
                    cout << i << ' ' << j << ' ' << k << ' ' << endl;
                    return 0;
            }
        }
    }
}

祝你学业进步

by wshiren @ 2022-08-11 21:55:25

在各位大佬的建议下，成功AC

@oier_lyb @WZRYWZWY @sin

#include <bits/stdc++.h>
using namespace std;

bool isPrime(int num){
    if(num < 2){
        return false;
    }
    for(register int i = 2; i <= sqrt(num); ++i){
        if(num % i == 0) return false;
    }
    return true;
}

int main(){
    int n = 29791;
    cin >> n;
    vector<int> vec(n+1);
    for(register int i = 1; i<vec.size(); ++i){
        if(isPrime(i)) vec[i] = 1;
        else vec[i] = 0;
    }
    for(register int i = 2; i < sqrt(n); ++i){
        if(vec[i] == 0) continue;
        for(register int j = 2; j < n; ++j){
            if(vec[j] == 0) continue;
            for(register int k = 2; k < n; ++k){
                if(vec[k] == 1 && i + j + k == n){
                    cout << i << ' ' << j << ' ' << k << ' ' << endl;
                    return 0;
                }
            }
        }
    }
}