P17455 [GESP202609 Level 5] Goldbach's Conjecture

As everyone knows, Goldbach's conjecture says that any even number greater than $2$ can be written as the sum of two prime numbers. For example: - $4=2+2$ - $6=3+3$ - $8=3+5$ - $10=3+7=5+5$ You surely want to know: for an even number $n$ greater than $2$, how many ways are there to write it as the sum of two primes? For example, $4$, $6$, and $8$ each have only one way, while $10$ has two ways. Please write a program to compute the answer. In this problem, we consider two representations different if and only if the sets of primes used in the two representations are different. That is, $10=3+7$ and $10=7+3$ are the same representation and must not be counted twice.

One line containing an even integer $n$ greater than $2$.

One line containing an integer, representing the number of ways to write $n$ as the sum of two primes.

For $40\%$ of the test points, $4 \le n \le 100$ is guaranteed. For all test points, $4 \le n \le 10^6$ is guaranteed. Translated by ChatGPT 5