欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

13行代码AC_Justifying the Conjecture Gym - 102394J(解题报告)

程序员文章站 2022-07-02 23:12:52
Problem DescriptionThe 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 writ....

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


题干

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