问题 25512 --数字转换

25512: 数字转换

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

题目描述

Dizzy和CodeWaySky在玩一个游戏,游戏的内容是对数字进行变换,变换的规则是这样的:
如果一个数x的约数和(不包括它本身,下同)比它本身小,那么x可以变成它的约数和;如果对于某个y>x且y的约数和为x,那么x也可以变成y。例如,4可以变为3,1可以变为7。
限定所有的游戏中的数字变换在不超过n的正整数范围内进行,他们的游戏从任意一个小于等于n的数字开始,每一轮都进行一次变换,不能有重复数字出现,直到游戏不能进行为止,现在他们俩想知道这个游戏最多可以进行多少轮(即求不断进行数字变换且没有重复数字出现的最多变换步数)。

输入

一个正整数n。

输出

最多变化的步数。

样例输入

7

样例输出

3

提示

    【样例说明】

一种方案为:4→3→1→7。



【数据范围】

n<=1 000 000。

来源

 

[提交][状态]