问题2134--哥德巴赫猜想

2134: 哥德巴赫猜想

[命题人 : ]
时间限制 : 1 sec  内存限制 : 128 MB

提交

题目描述

哥德巴赫1742年在给欧拉的信中提出了以下猜想:任一大于2的整数都可写成三个质数之和。
欧拉在回信中也提出另一等价版本,即任一大于2的偶数都可写成两个质数之和。常见的猜想陈述为欧拉的版本。
因现今数学已经不再使用“1也是素数这个约定,原本的猜想现在陈述为:任意大于2的偶数可以写成2个质数之和,任意大于5的整数可以分解成3个质数之和(n>5,n为奇数,n=3+(n-3),3为质数,n-3为偶数)。
现在你需要用上述猜想来判断给定的合数可以用几个奇质数组成。

输入

一个合数n( 5< n< 1000000000)

输出

输出一个整数表示n最少用几个奇质数组成

样例输入 Copy

114514

样例输出 Copy

2