最简分数_网易游戏雷火笔试题

【注意：本题按通过的Case比例给分】

分数的分子和分母为互质数的分数叫最简分数。最简分数的分数的分子与分母没有除1以外的其他公约数。最简分数又叫既约分数，既约分数可理解成已经约分过的分数，也就是分子和分母是互质数的分数。

例如：
2/3, 1/10, 99/100 等等都是最简分数
而
2/4, 5/10, 20/30 等等都不是最简分数

对于任意一个正整数N，以N为分母并以小于等于N的正整数作为分子的分数都有N个
例如，当N=6时，一共有以下6个分数：
1/6, 2/6, 3/6, 4/6, 5/6, 6/6
其中的最简分数有两个，分别是：
1/6, 5/6

我们定义一个叫做“最简分数比”的函数F，这个函数的定义是：

F(x) = (以x为分母并以小于等于x的正整数作为分子的最简分数个数) / x

例如，F(6) = 2/6 ~= 0.333333

在这个问题中，只有一个输入数据N，请计算出所有小于等于N的正整数中，最小的F(n)数值，换句话说，对1到N的所有正整数x都计算F(x)并找出这N个F值中的最小值Fmin

N = int(input()) p=[2,3,5,7,11,13,17,19,23,29,31] facp=[1] for i in range(len(p)): facp.append(p[i]*facp[-1]) res=1 for i in range(len(facp)-1,-1,-1): if N>=facp[i] and i>0: res=res*((p[i-1]-1)/p[i-1]) print("{:.6f}".format(res)+"\n")

最简分数

输入描述:

输出描述:

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题