寻找质因数的差异

Question

在使用Python的primefac模块时 - https://pypi.org/project/primefac/ 我注意到这段代码是有效的：

import sys
import primefac
n = 600851475143
factors = list(primefac.primefac(n))

但是这个不会：

import sys
import primefac
n = 19087688894909892783503691960213776632781962588843842839953893606139157282825376128877238229887486797933180624979637419997128020864299273315243907454874577263432419226852240380380880131843664800828228959920799327101817796594944161768692639537839544009100224905464911818390882192901883104039350105285757995782376058970382205463192526628231366854662473466838863987148898819243940809068605863725041711337107340279029811816555169181781669826715177100102639379572663639848699896757952171115689208069972249342540932428107175784150214806633479073061672324629925288020557720111253896992657435200329511186117042808357973613389
factors = list(primefac.primefac(n))

导致以下错误：

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "C:\Python27\lib\site-packages\primefac.py", line 677, in primefac
    f = multifactor(n, methods=methods, verbose=verbose)
  File "C:\Python27\lib\site-packages\primefac.py", line 596, in multifactor
    for p in procs: p.start()
  File "C:\Python27\lib\multiprocessing\process.py", line 130, in start
    self._popen = Popen(self)
  File "C:\Python27\lib\multiprocessing\forking.py", line 277, in __init__
    dump(process_obj, to_child, HIGHEST_PROTOCOL)
  File "C:\Python27\lib\multiprocessing\forking.py", line 199, in dump
    ForkingPickler(file, protocol).dump(obj)
  File "C:\Python27\lib\pickle.py", line 224, in dump
    self.save(obj)
  File "C:\Python27\lib\pickle.py", line 331, in save
    self.save_reduce(obj=obj, *rv)
  File "C:\Python27\lib\pickle.py", line 425, in save_reduce
    save(state)
  File "C:\Python27\lib\pickle.py", line 286, in save
    f(self, obj) # Call unbound method with explicit self
  File "C:\Python27\lib\pickle.py", line 655, in save_dict
    self._batch_setitems(obj.iteritems())
  File "C:\Python27\lib\pickle.py", line 687, in _batch_setitems
    save(v)
  File "C:\Python27\lib\pickle.py", line 286, in save
    f(self, obj) # Call unbound method with explicit self
  File "C:\Python27\lib\pickle.py", line 754, in save_global
    (obj, module, name))
pickle.PicklingError: Can't pickle <function factory at 0x00000000032520B8>: it's not found as primefac.factory
type(n)Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "C:\Python27\lib\multiprocessing\forking.py", line 381, in main
    self = load(from_parent)
  File "C:\Python27\lib\pickle.py", line 1384, in load
    return Unpickler(file).load()
  File "C:\Python27\lib\pickle.py", line 864, in load
    dispatch[key](self)
  File "C:\Python27\lib\pickle.py", line 886, in load_eof
    raise EOFError
EOFError

有人知道为什么会发生这种情况吗？

在两种情况下，type(n) 返回 <type 'long'>

- Employee

---

我相信，在这两种情况下，n 有正确的类型，但是那个库中使用的类型呢？ - Dominique

随机猜测：将活动代码（在导入之后）放置在if __name__ == "__main__":块中。Windows 在多进程方面存在一些问题。 - Michael Butscher

@MichaelButscher 没有任何变化 - Employee

在 MacOs 上运行，未引发任何异常。我认为这与 Windows 有关。 - knh190

Answer 1

以下是我的意见：

• 如果您还没有，请尝试导入gmpy2。

• 从您提供的项目页面中：

  GNU的因数分解命令无法分解大于2^127-1的任何数字

  这大约是1.7*10^38，比您所面临的数字要小得多。 因此，可能（我在这里推测）该软件包存在一些限制，并且那些报告其在某些操作系统上工作（目前为止是MacOS）的人也会遇到一些“dump”错误，这些错误使用CPython级别上的操作系统处理，使用一些“垃圾”内存值，导致他们认为这是有效的。

- LemonPy

Answer 2

函数factory在primefac.py文件中的multifactor函数内定义。

pickle.PicklingError: 无法将位于 0x00000000032520B8 的函数 factory 进行 Pickle，因为它没有被找到 primefac.factory。

Pickle仅适用于顶层函数。

如果您将此函数移至顶层，即将其移出primefac.py中的multifactor函数，则此错误将消失。

- Ajay Srivastava

---

我的系统挂了。进程消耗了所有的内存。所以，我放弃了。 - Ajay Srivastava

我刚刚强制退出了进程，因为我的系统也挂起了。但是为了确保您的答案是正确的并接受它，必须实现和证明其正确运行。 - Employee

@Lossofhumanidentity 我没有尝试过你的代码，但你是否尝试过使用一个更容易分解的数字？它仍然可能是一个巨大的数字，但有许多非常小的质因数。 - tobias_k

@tobias_k，请复制/粘贴您想要测试的数字，我将对其进行测试。 - Employee

虽然这并不重要，但是OP的例子是一个具有非常相似因子的半素数。因此Fermat或Hart的OLF很容易找到它。最新版本的yafu也可以找到它。一个因子: 138158202416323775732758181522345834049037787229131795417941446702298473258343563193135609927838924393215490081927911051242414284813908013710478543881939279495893465648447667821464399443365370563999639701664554440716709602014683969079330309194498696044593783004289298158663252552132414967582447904614532945373。 - DanaJ