题目:
如果一个分数的分子和分母的最大公约数是1,这个分数成为既约分数。例如3/4、1/8、7/1、都是既约分数。请问,有多少个既约分数,分子和分母都是1到2020之间的整数(包括1和2020)?
分析:
判断分子和分母的最大公约数是否为1,python可以用数学库中的gcd函数直接计算最大公约数。
range会减1因此写到2021
import math
c = 0
for i in range(1, 2021):
for j in range(1, 2021):
if math.gcd(i, j) == 1:
c += 1
print(c)
输出结果
2481215