13行代码AC_Justifying the Conjecture Gym - 102394J（解题报告）

励志用少的代码做高效表达

---

题干

Problem Description

The great mathematician DreamGrid proposes a conjecture, which states that:
Every positive integer can be expressed as the sum of a prime number and a composite number.
DreamGrid can’t justify his conjecture, so you are invited to write a program to verify it. Given a positive integer n, find a prime number x and a composite number y such that x+y=n.
A prime number is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. Note that 1 is neither a prime number nor a composite number.

Input

The input contains multiple cases. The first line of the input contains a single integer T (1≤T≤105), the number of cases.
For each case, the only line of the input contains a single integer n (1≤n≤109).

Output

For each case, print two integers x and y in a single line, where 1≤x,y<n. If there are multiple valid answers, you may print any of them. If there is no valid answer, print the integer −1 instead.

---

分析与思路

题意：给定一个数，若能其分解出质数+合数，则输出其中的一个组合， 否则输出-1

由于n是1e9的规模， 即便是线性规模，也会TEL， 因此要找规律。

水题嘛，不要想得太复杂

当n等于3、4、5时，直接特判就可以。

当n>5时， 如果其为偶数，那么一定能分解成2与(n-2)，2为质数，n-2必定为合数(因为它是偶数)； 如果其为奇数，那么一定能分解长3与(n-3)，3为质数，n-3必定为合数(因为它是偶数)，都满足条件。输出即可。

---

代码展示

#include<iostream> using namespace std; int main() { ios::sync_with_stdio(false); int T; cin>>T; while(T--) { int n; cin>>n; if(n==1||n==2||n==3||n==4||n==5) cout<<"-1"<<'\n'; else { if(n%2==0) cout << 2 << ' ' << n-2 << '\n'; else cout << 3 << ' ' << n-3 << '\n'; } } return 0; } 

本文地址：https://blog.csdn.net/weixin_43899069/article/details/109013136