# [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.

DaveA

```