Responsive image

问题 H: 整数拆分

问题 H: 整数拆分

时间限制: 1 Sec  内存限制: 256 MB
提交: 0  解决: 9
[提交][状态][讨论版][命题人:]

题目描述

我们规定f(x)（x≥2）表示整数x的除本身之外的最大因数。

例如，f(6)=3，f(25)=5，f(2)=1。

现在，给定一个整数n，请你将其拆分为K份n1,n2,…,nk（也可以不拆分，即k=1），要求：

  • n1+n2+…+nk=n
  • 对于 1≤i≤k，ni≥2 始终成立。
  • f(n1)+f(n2)+…+f(nk) 的值应尽可能小。

输出 f(n1)+f(n2)+…+f(nk) 的最小可能值。

输入描述

一个整数 n（2≤n≤2×109）。

输出描述

一个整数，表示f(n1)+f(n2)+…+f(nk) 的最小可能值。

样例输入

27

样例输出

3
[提交][状态]
ACM算法攻关部