P15059

A+B Problem（再升级）

难度 5 级小学动态规划入门背包DP 完全背包

讨论统计 29通过 39提交 74.4%通过率旧版界面

时间限制 1 秒 内存限制 128 MB

题目描述

给定一个正整数 $n$ ，求将其分解成若干个素数之和的方案总数。

输入

一行一个正整数 $n$ 。

输出

一行一个整数表示方案总数。

样例

样例 1

输入

输出

样例 2

输入

输出

提示

样例解释

存在如下三种方案：

$7=7$ 。
$7=2+5$ 。
$7=2+2+3$ 。

数据范围及约定

对于 $30\%$ 的数据 $1\le n\le 10$ 。
对于 $100\%$ 的数据， $1\le n\le 10^3$ 。

来源

luogu

上一题下一题