#B4141. [信息与未来 2016] 素数分解

[信息与未来 2016] 素数分解

题目描述

素数,又称质数,是指除 11 和其自身之外,没有其他约数的正整数。例如,2,3,5,7,132,3,5,7,13 都是质数,而 4,9,12,184,9,12,18 则不是。

虽然素数不能分解成除 11 和其自身之外整数的乘积,但却可以分解成更多素数的和。你需要编程求出一个正整数最多能分解成多少个互不相同的素数的和。

输入格式

一行一个正整数 nn

输出格式

一行一个正整数,表示 nn 最多能分解成多少个不同的素数的和。

21
4
128
9

提示

样例 1\textbf 1 解释

21=2+3+5+1121=2+3+5+11

数据范围

10n20010\le n\le 200

保证有解。

本题原始满分为 20pts20\text{pts}