[Tutor] project euler prime factorization problem

Dave Angel davea at ieee.org
Mon Aug 30 03:32:35 CEST 2010

Steven D'Aprano wrote:
> On Mon, 30 Aug 2010 05:31:00 am bob gailer wrote:
>>> My current reasoning was something of this sort:  Find all the
>>> factors of a number, then reduce them to just the prime factors
>> Very inefficient. IMHO the proper way is to generate a list of all
>> the prime numbers up to the square root of 600851475143, then test
>> each (starting with the largest and working down) till you discover a
>> factor. That then is the answer.
> Actually your approach is inefficient too, and it won't always work. 
> Consider what happens if you are asked for the prime factors of 101. 
> You would generate the primes up to 10:
> 2, 3, 5, 7
> but none of those are factors.
> <snip>
I agree about inefficient, but not "won't always work."

If you've got a list of all the primes up to the square root of n, and 
none of them are factors, then n is prime as well.  Not necessarily the 
next prime in the list, but prime nonetheless.  So perhaps you're 
objecting that Bob didn't say the else-portion of his algorithm -  He 
said "till you discover a factor" but neglected to say what it means if 
you don't.  If you don't, then the value 600851475143 is prime.  So the 
number would be its own largest prime factor.


More information about the Tutor mailing list