Problem2134--哥德巴赫猜想

2134: 哥德巴赫猜想

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MiB

Description

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

Input

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

Output

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

Sample Input Copy

114514

Sample Output Copy

2

Source/Category

admin