输入n的值,统计所有在正整数1和n之间能被6整除、但不能被4整除的数有多少个
时间: 2024-05-15 16:16:11 浏览: 105
找出100~200之间,所有既能被3整除还能被5整除的数,并统计出数量
算法1:
1. 初始化计数器count为0
2. 对于i从1到n,如果i能被6整除且不能被4整除,将count加1
3. 返回count作为结果
时间复杂度:O(n)
算法2:
1. 将n除以12得到商和余数
2. 计算从1到商×2中有多少个数能被6整除但不能被4整除,记为count1
3. 如果余数大于等于6,则计算从商×2+1到商×2+6中有多少个数能被6整除但不能被4整除,记为count2
4. 返回count1+count2作为结果
时间复杂度:O(1)
实现如下(采用算法2):
```python
def count_numbers(n):
quotient, remainder = divmod(n, 12)
count1 = quotient * 2
if remainder >= 6:
count2 = min(remainder - 6, 6) // 2 + 1
else:
count2 = 0
return count1 + count2
```
测试:
```python
assert count_numbers(6) == 1
assert count_numbers(10) == 1
assert count_numbers(12) == 2
assert count_numbers(19) == 3
assert count_numbers(24) == 4
assert count_numbers(25) == 4
assert count_numbers(30) == 5
```
阅读全文