logo AlgoBeat OnlineJudge
登录 注册

#215480. [CCC 2019 S2] Pretty Average Primes 优雅平均质数

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

对于若干给定的正整数 ,其中 ,请找出两个素数 ,使得 的平均值(算术平均数)。也就是说:

回顾:素数是一个整数 ,且仅能被 整除。例如, 是最前面的几个素数,而 都不是素数。

输入格式

第一行输入一个整数 ),表示测试用例的数量。

接下来 行,每行包含一个整数 )。

分中,有 分对应的数据满足所有

输出格式

输出共 行。第 行包含两个整数 ,中间用一个空格分隔。

必须满足:

都是素数。

若某个 存在多组可能的 ,输出任意一组即可。输出时 的顺序无关。

题目保证:对于每个 ,至少存在一组满足条件的解。

样例

样例输入 1

4
8
4
7
21

样例输出 1

3 13
5 3
7 7
13 29

数据范围与提示

样例输出说明

注意到:

同样也可以写成:

因此,上述任意一组都可以作为输出。

对于 ,除了 之外,不存在其他素数对能够使其平均值为

注释

你可能听说过哥德巴赫猜想(Goldbach’s Conjecture):任何大于 的偶整数都可以表示为两个素数之和。至今尚无已知证明。如果你想出名,可以在完成 CCC 之后去证明它。

本题可以用于验证该猜想,因为每个偶整数都可以写成:

而你的任务是找到两个素数 ,使得:

翻译来源:GPT 5.2。