求给定范围内含奇数个因数的元素个数的Python程序咨询

问题本质解析 #

先搞清楚核心逻辑：一个数的因数个数为奇数，当且仅当这个数是完全平方数。

原因很简单：

• 普通数的因数都是成对出现的，比如6的因数是1&6、2&3，总共4个（偶数）；
• 只有完全平方数会有一个重复的因数——它的平方根，比如9的因数是1、3、9，其中3是平方根，只算一次，总共有3个（奇数）。

所以这个问题可以直接转化为：统计给定区间内的完全平方数的数量。

解决方案思路 #

1. 找到区间左边界对应的最小完全平方数的平方根（向上取整）；
2. 找到区间右边界对应的最大完全平方数的平方根（向下取整）；
3. 如果左边界的平方根大于右边界的平方根，说明区间内没有完全平方数，结果为0；否则结果就是右边界平方根 - 左边界平方根 + 1。

举个例子：区间[2, 17]

• 最小的完全平方数是4（平方根2），最大的是16（平方根4），数量是4-2+1=3（对应4、9、16）。

Python代码实现 #

import math

def count_odd_factor_numbers(lower, upper):
    # 计算大于等于lower的最小平方根，向上取整
    start_root = math.ceil(math.sqrt(lower))
    # 计算小于等于upper的最大平方根，向下取整
    end_root = math.floor(math.sqrt(upper))
    # 处理无符合条件数的情况，返回非负数
    return max(0, end_root - start_root + 1)

# 示例运行
if __name__ == "__main__":
    low = int(input("输入范围左边界: "))
    high = int(input("输入范围右边界: "))
    print(f"拥有奇数个因数的元素个数: {count_odd_factor_numbers(low, high)}")

代码说明 #

• math.sqrt()用于计算平方根，math.ceil()确保我们得到第一个不小于左边界的平方数的根；
• math.floor()得到最后一个不大于右边界的平方数的根；
• max(0, ...)避免出现负数结果（比如区间[5,8]，start_root=3，end_root=2，此时返回0）。

内容的提问来源于stack exchange，提问作者Prasad Jadhav