#G1195. [GESP202609 五级] 哥德巴赫猜想

[GESP202609 五级] 哥德巴赫猜想

[GESP202609 五级] 哥德巴赫猜想

时间限制:1.0 s 内存限制:512.0 MB

题目描述

众所周知,哥德巴赫猜想是说,任何大于 2 的偶数都能写成两个质数(素数)之和。例如:

  • 4=2+24 = 2 + 2
  • 6=3+36 = 3 + 3
  • 8=3+58 = 3 + 5
  • 10=3+7=5+510 = 3 + 7 = 5 + 5

聪明的你肯定想知道,对于大于 2 的偶数 nn,它有多少种写成两个质数之和的方法。例如 4、6 和 8 都只有一种方法,10 有两种方法。请你编写程序计算这个问题的答案。

在本题中,我们认为两种方案不同,当且仅当两种分解方案包含的素数互不相同;即 10=3+710 = 3 + 7 和 10=7+310 = 7 + 3 是同一种方案,不能重复计数。

输入格式

一行,一个大于 2 的偶数 nn。

输出格式

一行,一个整数,表示将 nn 写成两个质数之和的方法数。

样例 #1

样例输入 #1

4

样例输出 #1

1

样例 #2

样例输入 #2

10

样例输出 #2

2

数据范围

测试点 数据范围 说明
1~4 4≤n≤1004 \le n \le 100 无
全部 4≤n≤1064 \le n \le 10^6