Difference in finding prime factors

Question

While working with the Python primefac module - https://pypi.org/project/primefac/

I noticed that this code works:

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

But this doesn't:

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

Resulting in the following error:

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

Does anybody know why is this happening?

In both cases type(n) returns <type 'long'>

Jarvisjary

I believe that, in both cases, n has the correct type, but what about the types, used in that library? – Aristaeus

Random guess: Place active code (after the imports) in a if __name__ == "__main__": block. Windows has some problems with multiprocessing. – Religiosity

@MichaelButscher nothing changes – Jarvisjary

Running on MacOs no exception raised. I believe it's something related to Windows. – Barbell

Answer 1

Here are my two cents:

• Try and import gmpy2, if you don't already have it.

• From the project page you linked to:

  GNU’s factor command won’t factor anything greater than 2^127-1

  Which is roughly 1.7 * 10^38, a significantly smaller number then the one you are being "dumped" on. So, it might be (I am speculating here) that there are limitations in that package and that people who report it working on some OS (MacOS, as of this moment) are also getting some "dump" error, that is handled using the OS on the CPython level, with some "junk" memory values, leading them to believe that this is working.

Mammy

Answer 2

The function factory is defined inside another function multifactor in primefac.py.

pickle.PicklingError: Can't pickle function factory at 0x00000000032520B8: it's not found as primefac.factory

Pickle works on top level functions only.

If you move this function to top level i.e. out of multifactor in primefac.py, then this error will be gone.

Mannie

Thank you for the clever observation. I've launched the script and haven't received any error so far, but the machine is still computing. As soon as I will see factors output on console I will accept you answer. BTW: Did you manage to get the script finish its job and see that the output was correct? My machine is still computing. – Jarvisjary

Machine is still computing and not returning... I'm still waiting – Jarvisjary

My system hanged. Process consumed all of the memory. So, I gave up. – Mannie

I just forced the process to exit because my system hanged as well. But in order to be sure that your answer is correct and accept it, proper functioning must be achieved and proved – Jarvisjary

@Lossofhumanidentity I did not try your code, but have you tried with a number that's easier to factor? It could still be a huge number, but with many very small prime factors. – Momus

@Momus copy/paste me the number you're thinking about and I will test it – Jarvisjary

@Lossofhumanidentity Just something like 2**largenumber*3**largenumber*5**...*7**... Just an idea to narrow down the problem. – Momus

Not that it matters, but OP's example is a semiprime with very similar factors. So Fermat or Hart's OLF finds it easily. As does latest yafu. One factor: 138158202416323775732758181522345834049037787229131795417941446702298473258343563193135609927838924393215490081927911051242414284813908013710478543881939279495893465648447667821464399443365370563999639701664554440716709602014683969079330309194498696044593783004289298158663252552132414967582447904614532945373. – Cowles