正约数定义: 一个正整数a,如果除了1和它本身,还有其它的正整数能够整除它,则这个正整数a就是合数;反之,如果除了1和它本身,没有其它的正整数能够整除它,则这个正整数a就是质数。那么一个数的正约数就是它的所有质因数和1。
对于一个正整数n,如果要求解它的正约数有哪些,最直接的方法就是先分解质因数,再求出所有因数。但是随着数字越来越大,这个方法就越来越低效。
很好,现在我们来介绍一种高效计算一个数的正约数的方法,以下是步骤:
- 求出这个数字n的平方根s
- 对于2~s之间的每个数,如果它是n的因数,则把数本身和n/数作为一对正约数输出,也就是输出(n/数,数)。
也就是说,正约数总数为s下整数 1。我们通过筛选出s下整数中的正约数,再从中筛选出比s大的正约数,即为n的所有正约数。
这样的计算方法可以将效率大大提升,对于大数也可以在较短时间内得出正约数。对于算法的完整代码,可以参考以下内容:
def get_factor(num): res = set() s = int(num ** 0.5) 1 for i in range(2, s): if num % i == 0: res.add(num // i) res.add(i) res.add(num) return resresult = get_factor(100)print(result)