时间限制	内存限制
`1000 ms`	`65536 KB`

# 题目背景

哥德巴赫猜想是 “世界三大数学猜想” 中唯一尚未被证明的猜想，被誉为是数学界最难证明的猜想之一，可以被表述为 “任一大于 2 的偶数都可写成两个素数之和”。1966 年，陈景润在《科学通报》上发表了有关哥德巴赫猜想 “1+2” 的证明，即 “任何一个充分大的偶数都可以表示成两个素数的和或者一个素数及一个二次殆素数的和”。1973 年，陈景润给出了 “1+2” 的详细证明，同时改进了 1966 年研究的数值结果。是年四月，中国科学院主办的《中国科学》上，公开发表了陈景润的论文 《大偶数表为一个素数及一个不超过二个素数的乘积之和》。这一结果被国际上誉为 “陈氏定理”。

# 题目描述

如果一个正整数可以分解为两个素数的乘积，则称之为半素数，如 $4,6,9,10,14,15,21, \cdots$ 等等。

请你验证陈氏定理：给出一个大于 $2$ 的偶数 $n$ ，输出所有的算式 $n=a+b$ ，要求 $a≤b$ ， $a,b$ 中一个是素数，且另一个是素数或半素数。

对于每个满足要求的算式 $n=a+b$ ：

若 $a,b$ 均为素数，则输出格式为 1+1: n=a+b ；
若 $a$ 为素数， $b$ 为半素数，则输出格式为 1+2: n=a+b ；
若 $a$ 为半素数， $b$ 为素数，则输出格式为 2+1: n=a+b 。

# 输入格式

一行一个大于 $2$ 的偶数 $n$ ，保证 $n≤10^5$ 。

# 输出格式

输出若干行，每行输出一个满足要求的算式 $n=a+b$ ，按照 $a$ 的升序顺序进行输出。

对于每个满足要求的算式 $n=a+b$ ：

若 $a,b$ 均为素数，则输出格式为 1+1: n=a+b ；
若 $a$ 为素数， $b$ 为半素数，则输出格式为 1+2: n=a+b ；
若 $a$ 为半素数， $b$ 为素数，则输出格式为 2+1: n=a+b 。

# 输入样例

# 输出样例

	1+2: 28=2+26
	1+2: 28=3+25
	1+1: 28=5+23
	1+2: 28=7+21
	2+1: 28=9+19
	1+1: 28=11+17
	1+2: 28=13+15

# 提示

可以参考书上判断素数的代码。

# 题解：线性筛素数

我们提前预处理出 $n$ 以内的所有素数和半素数，然后直接枚举即可。筛素数用线性筛法，筛半素数直接枚举素数因子。

时间复杂度： $O(n \sqrt n)$ 。

参考代码：

	#include <stdio.h>
	#include <stdbool.h>

	int n, primeCnt, prime[100010];
	bool notPrime[100010], isHalf[100010];

	void GetPrime(int lim)
	{
	notPrime[0] = notPrime[1] = true;

	for (int i = 2; i <= lim; ++ i)
	{
	if (!notPrime[i])
	prime[ ++ primeCnt] = i;

	for (int j = 1; j <= primeCnt && 1ll * i * prime[j] <= lim; ++ j)
	{
	notPrime[i * prime[j]] = true;

	if (i % prime[j] == 0)
	break;
	}
	}

	return;
	}

	void GetHalf(int lim)
	{
	for (int i = 1; i <= lim; ++ i)
	{
	if (!notPrime[i])
	continue;

	for (int j = 1; j <= primeCnt && 1ll * prime[j] * prime[j] <= i; ++ j)
	if (i % prime[j] == 0 && !notPrime[i / prime[j]])
	isHalf[i] = true;
	}

	return;
	}

	int main()
	{
	// freopen("J.in", "r", stdin);
	// freopen("J.out", "w", stdout);

	scanf("%d", &n);
	GetPrime(n);
	GetHalf(n);

	for (int i = 1; i <= (n >> 1); ++ i)
	{
	int j = n - i;

	if (!notPrime[i] && !notPrime[j])
	printf("1+1: %d=%d+%d\n", n, i, j);
	else if (!notPrime[i] && isHalf[j])
	printf("1+2: %d=%d+%d\n", n, i, j);
	else if (isHalf[i] && !notPrime[j])
	printf("2+1: %d=%d+%d\n", n, i, j);
	}

	return 0;
	}

质数线性筛数论