使用函数验证哥德巴赫猜想

Description

本题要求实现一个判断素数的简单函数，并利用该函数验证哥德巴赫猜想：任何一个不小于6的偶数均可表示为两个奇素数之和。最后给定两个整数m和n，按顺序输出满足条件的数，并按一定形式输出。（素数就是只能被1和自身整除的正整数。注意：1不是素数，2是素数。）

函数接口定义：

int prime( int p );

void Goldbach( int n );

其中函数prime当用户传入参数p为素数时返回1，否则返回0；函数Goldbach按照格式“n=p+q”输出n的素数分解，其中p≤q均为素数。又因为这样的分解不唯一（例如24可以分解为5+19，还可以分解为7+17），要求必须输出所有解中p最小的解。

Input

一行两个整数m和n。（6 <= m <= n <= 1000）。

Output

输出若干行，每行以“n=p+q”的格式输出。

Sample Input 1 

89 100

Sample Output 1

90=7+83
92=3+89
94=5+89
96=7+89
98=19+79
100=3+97

思路分析：

1.素数如何实现：首先了解一下素数的定义，遍历从2到一个值【这个值可以是根号下n，为了提高计算效率因为如果大于根号下n的部分其实属于是重复计算】，看是否能够被其中任意一个数整除；若能够被某个数整除，不是素数返回0，若都不能被整除则是素数返回1

2.Goldbach函数：从m到n进行遍历，只要遇到偶数就尝试拆分（为了节省算力和提高时间效率）因为如果拆分为一个偶数素数只有2，并且一个偶数减去2还是偶数（且因为这个偶数的限制条件是大于6），因此一定不是素数；所以我们可以从3开始遍历，每次自增2，尽量保证是素数以减少判断次数。（比如90 我们遍历应从3开始，判断3是素数之后开始判断87是否为素数...7是素数正巧83也是素数，打印输出并跳出循环）

代码实现：（C++）

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int prime(int p) {
    int flag = 1;
    for(int r = 2;r<=sqrt(p);r++) {
        if(p%r==0) {
            flag = 0;
            break;
        }
    }
    if(flag==1)return 1;
    return 0;
}
void Goldbach(int m,int n) {
    for(int i = m;i<=n;i++) {
        if(i%2==0) {
            //如果这个数是大于6的偶数，可以拆成两个素数之和
            for(int t = 3;t<=i/2;t+=2){
                if(prime(t)==1&&prime(i-t)==1) {
                    cout<<i<<"="<<t<<"+"<<(i-t)<<endl;
                    break;
                }
            }
        }
    }
}
int main() {
    int m,n;
    cin>>m>>n;
    Goldbach(m,n);
    return 0;
}

C语言：

#include<stdio.h>
int prime(int p){
	if(p<=1)
		return 0;
	for(int i=2;i*i<=p;i++)
		if(p%i==0)
			return 0;
			  return 1;
}

void Goldbach(int n){
	for(int i=2;i<n/2;i++){
		if(prime(i)&&prime(n-i)){
			printf("%d=%d+%d\n",n,i,n-i);
			break;
		}
	}
} 

int main(){
	int m,n;
	scanf("%d %d",&m,&n);
	if(m<6)m=6;
	if(m%2!=0)m++;
	for(int i=m;i<=n;i+=2)
		Goldbach(i);
	return 0;
}