求1到n范围内能被 5 或 6 或 8 整除的数的个数。
时间: 2023-04-21 14:03:07 浏览: 316
这道题目可以使用容斥原理来解决。首先,我们可以分别计算能被5、6、8整除的数的个数,然后再减去同时能被两个、三个、甚至三个以上数整除的数的个数,最终得到的结果就是1到n范围内能被5或6或8整除的数的个数。
具体来说,设能被5、6、8整除的数的个数分别为a、b、c,那么有:
a = n / 5
b = n / 6
c = n / 8
同时能被5和6整除的数的个数为n / lcm(5, 6),其中lcm表示最小公倍数。同理,能被5和8、6和8整除的数的个数分别为n / lcm(5, 8)和n / lcm(6, 8)。能被5、6、8同时整除的数的个数为n / lcm(5, 6, 8)。
因此,1到n范围内能被5或6或8整除的数的个数为:
a + b + c - (n / lcm(5, 6) + n / lcm(5, 8) + n / lcm(6, 8)) + n / lcm(5, 6, 8)
其中,lcm(5, 6) = 30,lcm(5, 8) = 40,lcm(6, 8) = 24,lcm(5, 6, 8) = 120。
最终的代码如下:
def count_numbers(n):
a = n // 5
b = n // 6
c = n // 8
ab = n // 30
ac = n // 40
bc = n // 24
abc = n // 120
return a + b + c - (ab + ac + bc) + abc
print(count_numbers(100)) # 输出31
阅读全文