← 返回题单

题单练习深度优先搜索-DFS

← 上一题下一题 →

A70666 | $素数分解$

来源编程题

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

素数，又称质数，是指除 1 和其自身之外，没有其他约数的正整数。例如 2 、 3 、 5 、 13 都是素数，而 4 、 9 、 12 、 18 则不是。 虽然素数不能分解成除 1 和其自身之外整数的乘积，但却可以分解成更多素数的和。 你需要编程 求出一个正整数最多能分解成多少个互不相同的素数的和。 例如， 21 = 2 + 19 是 21 的合法分解方法。 21 = 2 + 3 + 5 + 11 则是分解为最多素数的方法。 再比如： 128 ，最多可以分解为 9 个素数的和。

输入格式

n (10 \le n \le 200)。

输出格式

n 最多能分解成多少个不同的素数的和。

输入输出样例

输入 #1

输出 #1

输入 #2

输出 #2

C++ 编辑器

输入

输出