输入n的值,统计所有在正整数1和n之间能被6整除、但不能被4整除的数有多少个。
时间: 2024-05-02 21:20:17 浏览: 171
最大公约数能同时被m和n整除的最大数。-《C++清华大学-谭浩强》
算法1:
使用循环遍历1到n之间的所有数,统计能被6整除但不能被4整除的数的个数。
时间复杂度:O(n)
算法2:
注意到一个数既能被6整除又不能被4整除,等价于该数能被3整除但不能被2整除。因此,可以使用公式计算1到n之间能被3整除但不能被2整除的数的个数。
设a为n除以3的商,b为n除以6的商。则1到n之间能被3整除但不能被2整除的数的个数为a-b。
时间复杂度:O(1)
以下为算法2的Python代码实现:
```python
n = int(input())
a = n // 3
b = n // 6
count = a - b
print(count)
```
阅读全文