[Tutor] project euler prime factorization problem

[Steven D'Aprano]

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.

In the case of 600851475143, you wastefully generate 62113 prime numbers 
when you actually only need 224.

The right way is to start at 2, then 3, and so forth, working up rather 
than down. Don't forget that there can be repeated factors.



-- 
Steven D'Aprano