find all multiplicands and multipliers for a number

[jonas.thornvall at gmail.com]

Den lördag 11 april 2015 kl. 09:35:22 UTC+2 skrev Steven D'Aprano:
> On Sat, 11 Apr 2015 04:08 pm, Paul Rubin wrote:
> 
> > Steven D'Aprano <steve+comp.lang.python at pearwood.info> writes:
> >> 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]
> > 
> > This takes about 4 seconds on a Intel(R) Core(TM) i5-3230M CPU @ 2.60GHz
> > laptop (64 bit linux):
> 
> Nice for some who have fast machines, but on my old jalopy, your code takes
> 110 seconds, more than five times slower than mine. It also returns the
> wrong result:
> 
> [3, 3, 3, 3, 7, 19, 73, 87211, 262657, 1.4411518807585587e+17]
> 
> Oops, you have a float in there, how did that happen?
> 
> We can tell your code gives the wrong result. It claims that 7 is a factor
> of 2**111+1:
> 
> py> n = 2**111 + 1
> py> itertools.islice(fac(n), 0, 5)
> <itertools.islice object at 0xb7c8f914>
> py> list(itertools.islice(fac(n), 0, 5))
> [3, 3, 3, 3, 7]
> 
> 
> but that can't be right:
> 
> py> n % 7
> 2L
> 
> Seven in not a factor of 2**111 + 1.
> 
> The reason your code gives wrong results is that you perform true division /
> rather than integer division // which means that you with n a float, which
> loses precision:
> 
> py> (n/9) % 3  # nine is a factor
> 0.0
> py> (n//9) % 3  # exact, without rounding
> 1L
> 
> 
> 
> -- 
> Steven

Love it.