测试20000的时候最后一个数是0，题目AC

P1579 哥德巴赫猜想（升级版）

F_L_Bird @ 2024-03-20 16:52:21

代码如下：

#include<string>
#include<iomanip>
#include<iostream>
#include<cmath>
using namespace std;

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

int main(){
    int n;
    cin>>n;
    if(isPrime(n - 4))
    {
        printf("2 2 %d",n - 4);
        return 0;
    }
    else
    {
        for(int i = 3;i < n;i += 1)
        {
            for(int j = i;j < n;j += 1)
            {
                if(isPrime(i) && isPrime(j) && isPrime(n - i - j))
                {
                    printf("%d %d %d",i,j,n - i - j);
                    return 0;
                }
            }
        }
    }
    return 0;
}

跑测试的时候好奇时间复杂度输了20000

结果是：3 19997 0

抱着破罐子破摔的想法提交了之后AC

为什么会变成这样子呢？

by PengDave @ 2024-03-20 17:21:51

@F_L_Bird 20000是偶数

by chenbingjie @ 2024-03-21 16:53:08

@PengDave 首先，isPrime函数里要特判0,1,因为这两个数连循环都进不了。 main函数里的for j循环j<=n-i更简便

by chenbingjie @ 2024-03-21 18:41:07

#include<iostream>
#include<cmath>
using namespace std;
bool check(int k){
    if(k==2){
        return true;
    }
    if(k==1||k==0){
        return false;
    }
    for(int i=2;i<=sqrt(k);i++){
        if(k%i==0){
            return false;
        }
    }
    return true;
}
int main(){
    int a;
    cin>>a;
    for(int i=2;i<a;i++){
        if(check(i)){
            for(int j=2;j<=a-i;j++){
                if(check(j)&&check(a-i-j)){
                    cout<<i<<" "<<j<<" "<<a-i-j;
                    return 0;
                }
            }
        }
    }
    return 0;
}