On 3 July 2013 06:52, Greg Ewing <greg.ewing@canterbury.ac.nz> wrote:
Daniel Robinson wrote:
That cofactor would have to have a prime factor less than sqrt(n).
<facepalm> You're right, of course. I feel suitably enfoolished. </facepalm>
It took me a little while to understand what you were getting at. My way of thinking about this is that in every pair of factors either both are equal to sqrt(n) or one is less than sqrt(n) and the other greater.
But there is a slight error in the second implementation:
if all(n % p for p in takewhile(lambda p: p**2 < n, primes_seen)):
should be
if all(n % p for p in takewhile(lambda p: p**2 <= n, primes_seen)):
otherwise it thinks that perfect squares are primes.
Ah, yes. I had it right in the for/while version so I'm going to blame this typo on takewhile/lambda for obfuscating my code. :) Oscar