Python 没有像我预期的那样增加循环

Question

我有一些代码，它将一个整数作为输入并打印出该整数质因数的排序列表。

它几乎适用于所有数字，例如，当输入为 100 时，它将打印 [2, 2, 5, 5]，对于 1235632，它将输出 [2, 2, 3, 3, 343237]。

但是，对于更大的数字，它不会按顺序打印出因子，我不确定这是否是我忽略的代码中 Unresolved 问题，或者是否是其他问题。

例如，当我输入 1234567891011121314151617 时，它将输出 [3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 43, 109, 104281, 1394027]，这显然没有排序，我一生都无法弄清楚为什么。

我正在使用我认为是最新版本的 pycharm。

无论如何，这是代码:

from math import floor
from math import sqrt

n = int(input("Enter a number to be split into its prime factors"))
FList = []
k = 1

while n != 1:
    k = k + 1
    s = floor(sqrt(n))

    if k > s:
        FList.append(int(n))
        break

    if n % k == 0:
        n = n/k
        FList.append(k)
        k = 1

print(FList)

编辑:只是为了澄清，我宁愿修复程序，然后使用排序算法来帮助清理。

正如其他人所指出的，大数字的因子完全是垃圾，所以我想当前的问题是为什么它打印这些数字。

Answer 1

问题是您使用 / 进行除法，其结果是 float :

6/2
# 3.0

当您尝试对大数进行因式分解时，除以第一个因式 (3) 后得到的结果是:

1234567891011121314151617 / 3
# 4.115226303370404e+23

它是四舍五入的，因为 float 的精度有限。这就是为什么您现在可以多次将其除以 2。

您应该使用整数除法//，这将为您提供无限精度的精确商:

1234567891011121314151617 // 3
# 411522630337040438050539

所以，只需将代码更改为:

from math import floor
from math import sqrt

n = int(input("Enter a number to be split into its prime factors"))
FList = []
k = 1

while n != 1:
    k = k + 1
    s = floor(sqrt(n))

    if k > s:
        print('appending', n)
        FList.append(int(n))
        break

    if n % k == 0:
        n = n//k  # Use integer division here
        FList.append(k)
        k -= 1  # Try k again on next loop, no need to test smaller values again.

print(FList)

对于您尝试的数字，有一些很大的因素，因此可能需要很长时间...(实际上，它是 3*2*47*4993*584538396786764503...)