[牛课习题]查找组成一个偶数最接近的两个素数

题目描述

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

输入描述:

输入一个偶数

输出描述:

输出两个素数
示例
输入
20
输出
7
13

题目分析

首先应该判断出一个数是否为素数。这里判断素数的范围采用从2到开平方根n，如果这个区间有个数能使n能被整除，说明n不是素数；如果没有，n就是素数。
从这个偶数的1/2去向两边找合适的素数，这样就可以保证两素数差值最小，如果找到了跳出循环即可。

参考代码

#include <iostream>#include <math.h>using namespace std;bool isPrime(int n){    int sq = sqrt(n);    for(int i = 2; i <= sq; ++i)    {        if(n%i == 0)            return false;    }    return true;}int main(){    int num;    while(cin >> num)    {        int half = num/2;        int i = 0;        for(i = half; i > 2; ++i)        {            if(isPrime(i) && isPrime(num-i))                break;        }        cout << num-i << endl << i << endl;    }    return 0;}

更多相关文章

随机推荐