额……

P1579 哥德巴赫猜想(升级版)

SaberMJ @ 2022-08-06 20:06:20

情况

代码:

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

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

int main(){
    int n;
    cin >> n;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            for(int k=0; k<n; k++){
                if(prime(i) == true && prime(j) == true && prime(k) == true && i + j + k == n){
                    cout << i << " " << j << " " << k;
                    return 0;
                }
            }
        }
    }
    return 0;
}

by AdventureExtremeX @ 2022-08-06 20:08:50

这个难道不应该打质数表吗


by AdventureExtremeX @ 2022-08-06 20:11:38

WA的问题:j和k的初值应该取i和j(?还是其它问题

TLE:时间复杂度n^3,你需要用质数表降低时间复杂度


by AdventureExtremeX @ 2022-08-06 20:11:53

@cbh1008


by caramel_qwq @ 2022-08-06 20:15:20

@cbh1008 你家质数有0和1?


|