504051 - 切蛋糕

【题目描述】切蛋糕(cake)

小光有一块细长的蛋糕,长度为n。 有一些人要来小光家里吃蛋糕,小光把蛋糕切成了若干块(整数长度),然后分给这些人。为了公平,每个人得到的蛋糕长度和必须相等,且必须是连续的一段。但是,小光并不知道要有多少人来。他只知道,来的人数为n的约数,且小于n。 显然把蛋糕平均分成n块一定能满足要求。但是,小光想要分出的块数尽量少。现在小光想知道,他要把蛋糕分成至少多少块,才能使得不管多少人来都能满足要求。

输入

输入共一个整数n,表示蛋糕的长度。

输出

输出共一个整数, 表示分出的最少块数。

样例

输入

6

输出

4

输入

15

输出

7
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题