较为基础的题目。

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;
}

因为题目说了，是任何大于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(Tn\sqrt n)$，稍稍卡了一下常，时间是正常这个时间复杂度做法的$\frac{1}{4}$。

按照思路枚举模拟即可。#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;
}

一道基础的题目。

观察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);

}

首先写一个判断素数的布尔型函数。 输入用死循环，后面可以判断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;
}

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

#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;
}

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

#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;
}

这道题我们可以循环输入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; 
}

使用一般的算法来解题：

#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;
}

👍 可爱可爱可爱

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

#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;
}

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

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

#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();
}