【牛客网】查找组成一个偶数最接近的两个素数

浅浅的花香味﹌ 2022-01-20 21:23 153阅读 0赞

#### 题目描述 ####

任意一个偶数（大于2）都可以由2个素数组成，组成偶数的2个素数有很多种情况，本题目要求输出组成指定偶数的两个素数差值最小的素数对  
输入描述：输入一个偶数  
输出描述：输出两个素数

#### 示例 ####

> 输入：20  
> 输出：7 13

#### 解题思路 ####

本题首先需要判断素数，素数表示除过1和本身，不能被其它数整除。通过循环遍历来判断一个数是否为素数。最近的两个素数应该从最中间的位置开始向两边查找。

#### 完整代码 ####

##### 解题1 #####

#include <iostream>
    #include <cmath>
    using namespace std;
    
    bool IsOnly(int n)   //判断素数的函数
    {
    	for (int i = 2; i <= sqrt(n); i++)
    	{
    		if (n%i == 0)
    			return false;
    	}
    	return true;
    }
    
    int main()
    {
    	int n;
    	while (cin >> n)
    	{
    		int left = n / 2 ;  //中值左边的数
    		int right = n - left;    //中值右边的数
    		  //左边或右边的值不是素数，继续向两边找
    		while (!IsOnly(left) || !IsOnly(right))  
    		{
    			left--;
    			right++;
    		}
    		cout << left << endl;
    		cout << right << endl;
    	}
    	return 0;
    }

#### 解题2 ####

# include <iostream>
    #include <cmath>
    using namespace std;
    
    bool IsOnly(int n)    //判断素数函数
    {
    	for (int i = 2; i <= sqrt(n); i++)
    	{
    		if (n%i == 0)
    			return false;
    	}
    	return true;
    }
    
    int main()
    {
    	int n = 0;
    	while (cin >> n)
    	{
    		int a = n / 2;
    		int b = 0;
    		while (a)
    		{
    			b = n - a;      //每次重新计算右边的值
    			if (IsOnly(a) && IsOnly(b))
    			{
    				break;
    			}
    			a--;
    		}
    		cout << a << endl;
    		cout << b << endl;
    	}
    	return 0;
    }