find all multiplicands and multipliers for a number

[Steven D'Aprano]

On Sat, 11 Apr 2015 11:06 am, Dave Angel wrote:

> But the real place to get improvement is to only divide by primes,
> rather than every possible integer.  And once you've done the division,
> let q be the next value for dividend.  So you'll get a list like
> 
> [3, 3, 3, 37]
> 
> for the value 999


Prime factorization is a *hard* problem. If it wasn't, most of modern
technology that relies on encryption (like https, ssh, internet banking
etc.) would be trivially broken.

But for what it is worth, my pyprimes library can return the prime
factorization of numbers:

py> import pyprimes.factors
py> pyprimes.factors.factorise(1234567890)
[2, 3, 3, 5, 3607, 3803]
py> pyprimes.factors.factorise(9753124680)
[2, 2, 2, 3, 3, 3, 5, 13, 191, 3637L]

It may be a bit slow for very large numbers. On my computer, this takes 20
seconds:

py> pyprimes.factors.factorise(2**111+1)
[3, 3, 1777, 3331, 17539, 25781083, 107775231312019L]


but that is the nature of factorising large numbers.


http://code.google.com/p/pyprimes/source/browse/



-- 
Steven