题目：最大素数分解个数

一、题目说明

素数（又称质数）是指 除 1 和其自身之外，没有其他约数的正整数。 例如：

• 素数：2、3、5、13
• 非素数：4、9、12、18

虽然素数不能再分解成更小的正整数乘积，但一个正整数可以表示为多个互不相同的素数之和。

现在，给定一个正整数 n，请你编程计算：

n 最多可以分解成多少个互不相同的素数之和。

举例说明

• 当 n = 21 时：

  • 一种分解方式：21 = 2 + 19
  • 分解为最多素数的方式： 21 = 2 + 3 + 5 + 11 共 4 个素数

• 当 n = 128 时：

  • 最多可以分解为 9 个互不相同的素数之和

二、输入格式

n

• 一个整数 n，表示需要分解的正整数

• 数据范围：

  10 ≤ n ≤ 200
  

三、输出格式

一个整数

• 表示 n 最多能分解成 多少个互不相同的素数之和

四、样例输入

21

五、样例输出

4

六、样例说明

• 样例 1：

  输入：
  21
  输出：
  4
  

• 样例 2（仅说明）：

  输入：
  128
  输出：
  9
  

七、题目提示

• 每个素数 只能使用一次

• 素数的顺序不影响结果

• 需要找到 素数个数最多 的一种分解方式

• 本题适合使用：

  • 素数筛选
  • 递归 / 回溯（子集搜索）
  • 或动态规划思想