勵(lì)志用少的代碼做高效表達(dá)

---

題干

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.

---

分析與思路

題意：給定一個(gè)數(shù)，若能其分解出質(zhì)數(shù)+合數(shù)，則輸出其中的一個(gè)組合， 否則輸出-1

由于n是1e9的規(guī)模， 即便是線性規(guī)模，也會(huì)TEL， 因此要找規(guī)律。

水題嘛，不要想得太復(fù)雜

當(dāng)n等于3、4、5時(shí)，直接特判就可以。

當(dāng)n>5時(shí)， 如果其為偶數(shù)，那么一定能分解成2與(n-2)，2為質(zhì)數(shù)，n-2必定為合數(shù)(因?yàn)樗桥紨?shù))； 如果其為奇數(shù)，那么一定能分解長3與(n-3)，3為質(zhì)數(shù)，n-3必定為合數(shù)(因?yàn)樗桥紨?shù))，都滿足條件。輸出即可。

---

代碼展示

#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; }

努力只能及格，拼命才能優(yōu)秀！ 加油，陌生人！

總結(jié)

以上是生活随笔為你收集整理的13行代码AC_Justifying the Conjecture Gym - 102394J（解题报告）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。