Gcd guessing game - 题目详情 - xfxcy

ID: 2082

远端评测题

1000ms

256MiB

难度: (无)

上传者:

题目描述

给定一个数n ,有一个数x , ( 1<=x<=n ) 每次你可以猜在[1,n]中的数,假设是y，如果x==y，游戏结束，如果没猜中，则告诉你gcd(x,y)，然后继续猜，直到猜中为止。

现在问给定n的情况下，最坏情况下最少要多少次猜中

输入格式

N

输出格式

最坏情况下最少猜中次数

数据范围与约定

2 ≤ n ≤ 10000.