13 条题解

  • 22
    @ 2022-2-8 16:49:48

    较为基础的题目。

    int n;
bool prime[1000010];

void ensure_prime() {
  memset(prime, true, sizeof(prime));
  prime[0] = false;
  prime[1] = false;
  for (int i = 2; i <= 1000000; i++) {
    if (!prime[i]) continue;
    for (int j = 2; j <= 1000010; j++) {
      if (i * j < 1000010) prime[i * j] = false;
      else break;
    }
  }
}

int main() {
  ensure_prime(); // 考虑到数据范围较大，需要提前预计算质数列表
  cin >> n;
  while (n) { // 如果为 0 则退出
    for (int i = 3; i <= 1000010; i += 2) {
      if (prime[i] && prime[n - i]) {
        cout << n << " = " << i << " + " << n - i << endl;
        break;
      }
    }
    cin >> n;
  }
  return 0;
}
  • 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}。

    • 3
      @ 2022-11-26 11:34:41

      按照思路枚举模拟即可。#5竟然给我过了。

      #include <bits/stdc++.h>
#define min(a, b) (a<b ? a : b)
#define max(a, b) (a>b ? a : b)
using namespace std;

int n;

bool isPrime(int x){ // 简单的判断质数，新手必会
	for (int i=2; i*i<=x; i++)
		if (x%i==0) return false;
	return true;
}

void print(int a){
	for (int i=3; i<=a-2; i+=2){ // 特判2的情况
		if (isPrime(i) && i==a-2){
            cout<<a<<" = 2 + "<<i<<endl;
			return;
		}
	}
	for (int i=3; i<=a-3; i+=2){ // 一般情况
		if (isPrime(i) && isPrime(a-i)){
            cout<<a<<" = "<<min(a-i, i)<<" + "<<max(a-i, i)<<endl;
			return;
		}
	}
}

int main(){
	while (cin>>n && n/*这一步是为了结束输入，完整写法为n!=0*/) print(n);
	return 0;
}
      • 3
        @ 2021-11-3 20:07:34

        一道基础的题目。

        观察n<=10^6,所以可以先用线性筛把质数先全部预处理出来。

        对于每个n暴力枚举每个质数，如果n-p[i]也是质数则输出，易证这是符合题目要求b-a最大的解。

        CODE

        bj[1]=1;

for (int i=2;i<=N;i++) { // 线性筛

	if (!bj[i]) p[++tot]=i;

	for (int j=1;j<=tot&&p[j]*i<=N;j++) bj[i*p[j]]=1;

} scanf("%d",&n);

while (n) {

	for (int i=1;i<=tot&&p[i]<n;i++)

		if (!bj[n-p[i]]) {printf("%d = %d + %d\n",n,p[i],n-p[i]); break;}

	scanf("%d",&n);

}
        • 1
          @ 2025-4-12 9:01:10 
          #include <iostream>
#include <vector>
using namespace std;

const int MAXN = 1e6 + 5;
vector<bool> isPrime(MAXN, true);

// 埃拉托斯特尼筛法求素数
void sieve() {
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i < MAXN; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j < MAXN; j += i) {
                isPrime[j] = false;
            }
        }
    }
}

// 验证哥德巴赫猜想
void verifyGoldbach(int n) {
    for (int a = 3; a <= n / 2; a += 2) {
        int b = n - a;
        if (isPrime[a] && isPrime[b]) {
            cout << n << " = " << a << " + " << b << endl;
            return;
        }
    }
    cout << "Goldbach's conjecture is wrong" << endl;
}

int main() {
    sieve();
    int n;
    while (cin >> n && n != 0) {
        verifyGoldbach(n);
    }
    return 0;
}

          这道题的核心是验证哥德巴赫猜想，对于输入的偶数，要把它拆成两个奇素数之和，并且在有多组解时输出两素数差值最大的那一组。可以先找出所有小于给定数的素数，再去遍历找出符合条件的素数对。 代码解释： 埃拉托斯特尼筛法：借助sieve函数来找出所有小于MAXN的素数，把结果存于isPrime数组中。 验证哥德巴赫猜想：verifyGoldbach函数从 3 开始遍历奇数a，计算b = n - a，若a和b都是素数，就输出结果并返回。 主函数：先调用sieve函数预处理素数，接着持续读取输入，直至遇到 0 为止，对每个输入调用verifyGoldbach函数进行验证。 复杂度分析： 时间复杂度：筛法的时间复杂度为:O(NloglogN) 对于每组数据，验证的时间复杂度为 O(N) 空间复杂度： O(N) 主要用于存储素数标记数组。

          • 1
            @ 2024-10-7 13:13:57

            首先写一个判断素数的布尔型函数。 输入用死循环，后面可以判断x是否为0，直接return 0。 判断时用函数来处理a和x-a两个数就ok了

            #include<bits/stdc++.h>
using namespace std;
bool su(int a){
	if(a<2) return false;
	for(int i=2;i*i<=a;i++){
		if(a%i==0){
			return false;
		}
	}
	return true;
}
int main(){
    
    while(true){
        int a=3;
        int x;
        cin >> x;
        if(x==0) return 0;
        cout<<x<< " = ";
        int n=x-3;
        while(a<=n){
            if(su(a) and su(x-a)){
                cout << a << " + " << x-a << endl;
                break;
            }
            a+=2;
        }
    }
    return 0;
}
            • 1
              @ 2024-3-31 19:20:11

              时间复杂度较高，但是简单易懂。

              #include<iostream>
using namespace std;
const int maxl = 20;
int n = 1,a[maxl];
bool isprime(int m)
{
	if(m==1)return false;
	for(int i=2;i*i<=m;i++)if(m%i==0)return false;
	return true;
}
int main()
{
	while(cin>>a[n]&&a[n]!=0)n++;
	for(int i=1;i<=n-1;i++)
	{
		bool flag = 1;
		for(int j=3;j<=a[i]/2;j++)
		{
			if(isprime(j)&&isprime(a[i]-j))
			{
				cout<<a[i]<<" = "<<j<<" + "<<a[i]-j<<endl;
				flag = 0;
				break;
			}
		}
		if(flag)cout<<"Goldbach's conjecture is wrong\n";
	}
	return 0;
}
              • 0
                @ 2023-9-27 12:28:49

                👍 可爱可爱可爱

                • 0
                  @ 2023-1-21 12:42:20

                  解决这道题很简单，筛法都不用，详情见代码：

                  #pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
bool isPrime(int x){
	if(x<2)return false;
	for(int i=2;i*i<=x;i++){
		if(x%i==0)return false;
	}return true;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	while(cin>>n){
		if(n==0)break;
		cout<<n<<" = ";
		for(int i=3;i<=n;i++){
			if(isPrime(i)&&isPrime(n-i)){
				cout<<i<<" + "<<n-i<<endl;
				break;
			}
		}
	}
	return 0;
}
                  • 0
                    @ 2022-5-29 16:04:56

                    这道题我们可以循环输入n，直到n为0。对于每次输入暴力枚举每个相加是n的数，接着判断它们是否都是质数。

                    #include<bits/stdc++.h>
using namespace std;
bool isprime(int n){//质数判断函数
	if(n==0 or n==1){//0和1特判
		return 0;
	}
	for(int i=2;i<n;i++){//枚举因数
		if(n%i==0)return 0;//有除了1以外的因数就返回0
	}
	return 1;//返回1
}
int n=-1;//否则不会进while循环
int main(){
    while(n!=0){//循环
    	cin>>n;
    	if(n==0){//是0就退出
    		break;
		}
		for(int i=0;i<=n;i++){//枚举加数
			if(isprime(i) and isprime(n-i)){
				cout<<n<<" = "<<i<<" + "<<n-i<<endl;//输出，注意格式
				break;//找到就退出
			}
		}
	}
	return 0; 
}
                    • 0
                      @ 2022-4-25 19:13:39

                      使用一般的算法来解题：

                      #include<bits/stdc++.h>
using namespace std;
bool is_prime(int n)
{
	for (int i=2;i*i<=n;i++)
	{
		if (n%i==0)
		{
			return 0;
		}
	}
	return 1;
}
int main()
{
	int n,i;
	while (cin>>n&&n!=0)
	{
		i=3;
		while (is_prime(i)==0||is_prime(n-i)==0)
		{
			i+=2;
		}
		printf("%d = %d + %d\n",n,i,n-i);
	}
	return 0;
}
                      • -3
                        @ 2022-5-1 17:31:09

                        一道很简单的题目，上代码：

                        #include <iostream>
#include <algorithm>
using namespace std;
bool is_prime(int x) {
    if (x < 2 || (x > 2 && x % 2 == 0)) return false;
    for (int i = 3; i * i <= x; ++i)
        if (x % i == 0) return false;
    return true;
}
int main() {
    int n;
    while (~scanf("%d", &n)) {
        if (n == 0) break;
        bool flag = false;
        for (int i = 3; i <= n / 2; i += 2)
            if (is_prime(i) && is_prime(n - i)) {
                printf("%d = %d + %d\n", n, min(i, n - i), max(i, n - i));
                flag = true;
                break;
            }
        if (!flag) puts("Goldbach's conjecture is wrong.");
    }
    return 0;
}

                        基础知识：质数（素数）的判断

                        • -4
                          @ 2022-3-28 11:25:08

                          这么简单的题目，何必写那么复杂呢？

                          #include <iostream>
using namespace std;
bool zhi(int a){
	if(a<=1)return false;
	for(int i=2;i*i<=a;i++)if(a%i==0)return false;
	return true;
}
int main(){
	int n;
	cin>>n;
	if(n==0)return 0;
	for(int i=1;i*2<=n;i++)if(zhi(i)&&zhi(n-i)){cout<<n<<" = "<<i<<" + "<<n-i<<endl;break;}
	return main();
}
                          • @ 2022-11-11 19:48:27

                            复杂度错的吧，你的第一层循环枚举一个 ii 需要 O(n)O(n) 的时间，然后你还得判断 ii 是否为素数，总时间复杂度为 O(nn)O(n\sqrt n)，显然这个时间复杂度无法通过 n≤106n\le 10^6 吧。

                        • 1

                        哥德巴赫猜想

                        信息

                        ID
                        197
                        时间
                        1000ms
                        内存
                        256MiB
                        难度
                        2
                        标签
                        递交数
                        662
                        已通过
                        240
                        上传者
                        1. 关于
                        2. 联系我们
                        3. 隐私
                        4. 服务条款
                        5. 版权申诉
                        6. Language
                        7. 兼容模式
                        8. 主题
                        2. © 2021-2025 Hydro.ac
                        5. Worker 0 in 107ms
                        6. Hydro v5.0.0-beta.1-401bb50-dirty Professional