计算一个非常大的整数的质因数

Question

我在使用 Python 时遇到了一个有趣的问题。我的任务是计算给定数字的所有质因数。这是我的代码：

import math

def func(number):
    while number % 2 == 0:
        number = number / 2
        print("2")

    for i in range(3, math.ceil(math.sqrt(number)) + 1, 2):
        while number % i == 0:
            number = number / i
            print(i)

    if number > 2:
        print(str(int(number)))

正常情况下这段代码可以正常工作，没有问题。但是，假设我们将 211,111,122,222,223,420 传递给 func。它将打印这些因素：2, 2, 2, 2, 2, 2, 19, 97, 178980536338。这显然是不正确的，因为我们要找到其因子的数字以零结尾，这意味着它的因子中必须至少有一个 5。正确的？事实上，如果将打印的因子相乘，结果将是 211,111,122,222,223,424（比传递的数字多四个单位）。我做错了什么？

Answer 1

使用 // 而不是 /。在 Python 3 中，/ 运算符为您提供了一个浮点数，这会导致不准确。如果您改用 //，您将坚持使用整数，这会给您正确的答案。

def func(number):
    while number % 2 == 0:
        number = number // 2
        print(2)
    for i in range(3, math.ceil(math.sqrt(number)) + 1, 2):
        while number % i == 0:
            number = number // i
            print(i)
    if number > 2:
        print(number)

func(211111122222223420)

给予

计算一个非常大的整数的质因数

Calculating the prime factors of a very big integer

python

math

prime-factoring