思路分析

这个问题可以根据质数的数量 $m$ 进行分类讨论，从最小的可能值 $m=1$ 开始逐步分析。这个解法依赖于数论中的一些结论，特别是哥德巴赫猜想。

1. 当 $m=1$ 时： 如果 $n$ 可以表示为 $1$ 个质数的和，那么 $n$ 本身必须是一个质数。因此，我们的第一步是检查输入的 $n$ 是否为质数。如果是，那么最小的 $m$ 就是 $1$。 对于 $n \le 10^9$ 的范围，我们可以通过试除法来高效地判断质数：只需检查从 $2$ 到 $\sqrt{n}$ 是否存在 $n$ 的因子即可。

2. 当 $m=2$ 时： 如果 $n$ 不是质数，我们接着考虑它是否能表示为 $2$ 个质数的和，即 $n = p_1 + p_2$。这里需要分两种情况讨论：

题目内容

找到一个最小的$m$，使得存在一个正整数序列 {$a_1,a_2,...,a_m$}，满足：

• $a_1+a_2+...+a_m=n$

• $a$ 中的每个元素都是质数。

输入描述

输入一行一个整数 $n(2 ≦n≦10^9)$ 。

输出描述

输出一行一个整数，代表最小的满足条件的 $m$ 。

样例1

输入

9

输出

2

说明

可以构造 $a=${$7,2$}，其中 $7+2=9$ ，且 $7$ 和 $2$ 都为质数。

可以证明不存在长度小于 $2$ 的满足条件的序列。

样例2

输入

2

输出

1

样例3

输入

27

输出

3