시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB30015714254.406%

문제

The goal of this program is to find all unique ways to represent a given even number as the sum of two prime numbers. A prime number is an integer greater than 1 that is evenly divisible by only itself and 1. The first few prime numbers are 2, 3, 5, 7, 11,. . . The German mathematician Christian Goldbach (1690-1764) conjectured that every even number greater than 2 can be represented by the sum of two prime numbers. (This conjecture has never been proved nor has a counterexample ever been found. As such, you may assume it is true for the cases considered in this problem.) There may be several ways to represent a given even number by the sum of primes. For example, the even number 26 may be represented as 3 + 23, 7 + 19, or 13 + 13.

입력

Input starts with an integer n (1 ≤ n ≤ 100) indicating the number of cases. The following n lines each contain a test case of a single even number x (4 ≤ x ≤ 32000).

출력

For each test case x, give the number of unique ways that x can be represented as a sum of two primes. Then list the sums (one sum per line) in increasing order of the first addend. The first addend must always be less than or equal to the second to avoid duplicates. Print a blank line between each pair of test cases.

예제 입력 1

3
4
26
100

예제 출력 1

4 has 1 representation(s)
2+2

26 has 3 representation(s)
3+23
7+19
13+13

100 has 6 representation(s)
3+97
11+89
17+83
29+71
41+59
47+53

출처

ICPC > Regionals > North America > North America Qualification Contest > ACM-ICPC North America Qualifier 2013 C번

  • 문제를 만든 사람: Tom Fuller