用户登录
用户注册

分享至

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

  • 作者: 墨梅72529213
  • 来源: 51数据库
  • 2021-07-12

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


题干

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

本文地址:http://www.51sjk.com/Upload/Articles/1/0/248/248852_20210624000922620.jpg

软件
前端设计
程序设计
Java相关