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 -- https://mail.python.org/mailman/listinfo/python-list