50012 哥德巴赫猜想

题目描述

哥德巴赫猜想:

任何大于4的偶数都可以拆成两个奇素数之和。比如:

8=3+5
20=3+17=7+13
42=5+37=11+31=13+29=19+23

你的任务是:验证小于 的数满足哥德巴赫猜想。

输入格式

多组数据,每一行一个数n, 读入以0结束

输出格式

对于每组数据,输出形如n=a+b,其中a、b是奇素数。若有多组满足条件的a、b,输出b-a最大的一组。

若无解,输出”Goldbach’s conjecture is wrong.”

样例

样例输入

8
20
42
0

样例输出

8 = 3 + 5
20 = 3 + 17
42 = 5 + 37

数据范围与提示

对于30%的数据:

对于60%的数据:

对于80%的数据:

对于100%的数据: 验证的数据组数不超过100

分类标签

[函数]

C++题解代码

#include <bits/stdc++.h>
using namespace std;

int a;
int c;
int b;
bool d;


bool fn2(int y) {
  b = sqrt(y);
  for (int j = 2; j <= b; j++) {
    if ((y%j) == 0) {
      return false;
    }
  }
  return true;
}

void fn(int x) {
  for (int i = 2; i < x; i++) {
    if ((fn2(i)) && (fn2((x-i)))) {
      cout<<x;
      cout<<" = ";
      cout<<i;
      cout<<" + ";
      cout<<(x-i);
      return;
    }
  }
  cout<<"Goldbach’s conjecture is wrong.";
}

// The main procedure
int main() {
  cin>>a;
  d = true;
  while (a != 0) {
    if (d) {
      d = false;
    } else {
      cout<<'\n';
    }
    fn(a);
    cin>>a;
  }
  return 0;
}

Blockly题解代码图片