计算一个整数有多少个因子

Question

所以我编写了一个函数来确定一个数字有多少个因子并列出该数字。但是我的函数没有输出正确的信息。

def num_factors(integer):
    result = 0
    for i in range(1,integer+1):
        if integer%i == 0:
            result +=1
    return result

print(num_factors(5))
print(num_factors(6))
print(num_factors(97))
print(num_factors(105))
print(num_factors(999))

由于某种原因它正在输出：

什么时候应该输出：

Answer 1

问题是您正在计算除以 1 和测试整数本身。

您需要减去 2 或跳过 1 和 integer 以获得您想要的输出：

def num_factors(integer):
    result = 0
    for i in range(2,integer): # skips 1 and integer...
        if integer%i == 0:
            result +=1
    return result

而甚至更好是认识到对于integer的每个x * y我们只需要找到其中一个（即， 16 具有 2、4 和 8 作为因子。计算 2 两次 (2 x 8=16) 和 4 一次 (4 x 4=16)) 并且由于一个将小于或等于 integer 的平方根只是循环到 integer 的平方根并递增 2 而不是递增 1 并且只进行一小部分测试（并使结果快 1000 倍):

def num_factors(integer):
    result = 0
    stop=int(float(integer)**0.5)
    for i in range(2,stop+1):
        if integer%i == 0:
            result +=2
    if stop*stop==integer: result-=1    
    return result

for x in (5,6,97,105,999):
    print(f'{x}: {num_factors(x)}')

打印：

顺便说一句：实际上，customary 将 1 和整数本身算作因子。所以所有这些结果应该是 +2 并且你原来的解决方案实际上是正确的。要使上述解决方案正确，只需从 result=2

开始

Answer 2

在行 for i in range(1,integer+1): 中，您循环遍历 1 和您的整数之间的所有数字，包括 1 和您的整数，它们当然是因子。

例如，如果 integer = 5，您将遍历 1、2、3、4 和 5。其中 1 和 5 当然都是 5 的因子。

您可以将行编辑为 for i in range(2,integer): 以修复错误。生成的代码如下所示：

def num_factors(integer):
    result = 0
    for i in range(2,integer):
        if integer%i == 0:
            result +=1
    return result

print(num_factors(5))
print(num_factors(6))
print(num_factors(97))
print(num_factors(105))
print(num_factors(999))

虽然正如评论中有人建议的那样，您可以进一步减少搜索 space。

Answer 3

试试这个：

num_factors=lambda integer : len([e  for e in range(1,integer) if integer%e==0 and e not in [1,integer]])



print(num_factors(5))
print(num_factors(6))
print(num_factors(97))
print(num_factors(105))
print(num_factors(999))

Answer 4

我会这样做：

def num_factors(integer):
    for i in range(1, integer, 1):
        if integer % i == 0:
            print(i)

print(num_factors(5))
print(num_factors(6))
print(num_factors(97))
print(num_factors(105))
print(num_factors(999))

Answer 5

sympy 提供此函数来查找质因数。

>>> from sympy.ntheory import factorint
>>> factorint(6008)   # 6008 = (2**3) * (751**1)
{2: 3, 751: 1}

Answer 6

好的，这不是您现在真正要问的问题，但它可能是您的下一个问题。如果您的整数很小，您的算法可以正常工作，但是当您的整数很大时呢？假设 integer = 1_200_000_000?

您需要找到整数的质因数分解：

integer = p1**q1 * p2**q2 * p3**q3 * .....

因子个数（包括1和整数本身）为

(q1 + 1)(q2 + 1)(q3 + 1)....

自1,200,000,000 = (2**10)(3**1)(5**8)以来，因子个数为(11 * 2 * 8) = 176.

计算一个整数有多少个因子

Counting how many factors an integer has

python

factors