70pts求调

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

abcdefghik @ 2024-09-23 22:10:42

#include <bits/stdc++.h>
using namespace std;
int f(int x) {
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0) return 0;
    return 1;
}
int main() {
    //freopen(".in","c",stdin);
    //freopen(".out","w",stdout);
    int n;
    cin >> n;
    if (f(n - 4)) {
        cout << 2 << ' ' << n - 4;
    }
    for (int i = 3; i < n; i++) {
        if (i % 2 == 1 && f(i)) {
            for (int j = 3; j < n; j++) {
                if (j % 2 == 1 && f(j)) {
                    int k = n - i - j;
                    if (f(k) && k % 2 == 1) {
                        cout << i << ' ' << j << ' ' << k;
                        return 0;
                    }
                }

            }
        }

    }
    return 0;
}

by litangzheng @ 2024-09-23 22:21:04

这道题用素数筛，你的原始方法会超时。

by _luogu_huowenshuo_ @ 2024-09-24 21:00:13

#include<bits/stdc++.h>
using namespace std;
bool c(int n)
{
    for(int i=2;i*i<=n;i++)
        if(n%i==0)
            return false;
    return true;
}
int main()
{
    int n;
    cin >> n;
    for(int i=2;i<=n;i++)
        for(int j=2;j<=n;j++)
            for(int k=2;k<=n;k++)
                if(i+j+k==n&&c(i)&&c(j)&&c(k))
                {
                    cout << i << " " << j << " " << k;
                    return 0;
                }
    return 0;
}

@LTZ_DSG 为啥我这代码AC了，暴力O(n^3\sqrt{n})

by litangzheng @ 2024-09-24 21:30:27

@huowenshuo 看错了，他从3开始枚举所以错了。（还有一个蜜汁特判）

|