Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Difference in finding prime factors

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'>

like image 665
Employee Avatar asked Jan 18 '19 12:01

Employee


People also ask

How is finding the factors of a number different from finding the prime factorization of a number?

Factors of a number are the numbers that divide the given number without leaving any remainder. Prime factorization of a number is the process of writing all the prime factors of that number that can be multiplied to get back the given number.

What is the difference between the prime factors of 39?

39 ÷ 3 = 13, 3 and 13 are prime numbers, so we cannot proceed with the division method. Thus, the prime factorisation of 39 can be expressed as 3 × 13.


2 Answers

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.

like image 177
Ajay Srivastava Avatar answered Sep 19 '22 22:09

Ajay Srivastava


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.

like image 21
LemonPy Avatar answered Sep 16 '22 22:09

LemonPy