[Tutor] project euler prime factorization problem

[Dave Angel]

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.

DaveA