10 条题解

  • 5
    @ 2023-1-3 9:21:58

    因为题目说了,是任何大于4 的偶数都可以拆成两个奇素数之和,所以不需要特判有2的情况。

    证明

    前置结论:一个偶数可以被拆成两个奇数相加或两个偶数相加,但不能被拆成一个奇数和一个偶数相加。(请自行证明,很容易)

    因为:唯一的偶素数是2,

    所以:一个偶数能被拆成两个偶素数相加,当且仅当这个偶数是4(=2+2)。

    因为:一个偶数可以被拆成两个奇数相加或两个偶数相加,但不能被拆成一个奇数和一个偶数相加,

    又因为:由两个偶素数相加得到的数只有4,不在题目的数据范围内,

    所以:在题目的数据范围内,一个偶数只能被拆成两个奇素数相加。

    因为:在题目的数据范围内,一个偶数只能被拆成两个奇素数相加,

    又因为:2是偶数,

    所以:在题目的数据范围内,我们不需要考虑2。

    代码

    说了这么多,上!代!码! (其实因为证明中提到了,在题目的数据范围内,一个偶数只能被拆成两个奇素数相加,所以有偶数的情况代码中直接跳过)

    #include<iostream>
    using namespace std;
    bool isprime(int x){
        if(x<=1)    return false;
        for(int i=3;i*i<=x;i+=2){
            if(x%i==0) return false;
        }
        return true;
    }
    int main(){
        int n;
        while(cin >> n && n){
            cout << n << " = ";
            int p=3;
            while(!isprime(p) || !isprime(n-p)) p+=2;
            cout << p << " + " << n-p << '\n';
        }
        return 0;
    }
    

    时间复杂度

    O(Tnn)O(Tn\sqrt n),稍稍卡了一下常,时间是正常这个时间复杂度做法的14\frac{1}{4}

    信息

    ID
    197
    时间
    1000ms
    内存
    256MiB
    难度
    2
    标签
    递交数
    378
    已通过
    153
    上传者