11351: 【原1351】丁姐猜想

题目

题目描述

author: SSY 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1351

Description

在1742年给欧拉的信中哥德巴赫提出了以下猜想：任一大于2的偶数都可写成两个质数之和。

同时部分奇数也能写成两个质数的和。丁姐觉得，找出这些奇数的规律自己就能够名垂青史了。

你现在要做的是，对于给定一个数N，分解成两个质数和，并且这两个质数的差的绝对值要尽量小。如果这个数无法分解成两个质数的和，则输出一个“NO”（不含双引号）。

Input Format

输入只有一个数N。

Output Format

输出一个NO或者用空格分开的两个质数，小的质数在前。

Sample Input

54749110

Sample Output

27374261 27374849

yyong119's solution

#include <cstdio>
#include <cmath>

bool IsPrime(int number) {

    int max_limit = (int)sqrt(number);
    for(int i = 2; i <= max_limit; ++i)
        if(number % i == 0)
            return false;
    return true;
}

int main() {

    int number, res1, res2;
    scanf("%d", &number);
    if(number % 2 == 0) {
        for(res1 = res2 = number / 2; true; --res1, ++res2)
            if(IsPrime(res1) && IsPrime(res2)) {
                printf("%d %d", res1, res2);
                return 0;
            }
    }
    else if(IsPrime(number - 2))
            printf("%d %d", 2, number - 2);
        else
            printf("NO");
    return 0;
}