Project euler no. 3

[Dave Angel]

Kee Nethery wrote:
> <div class="moz-text-flowed" style="font-family: -moz-fixed">in 
> checkPrime what do you return when "x" is less than 2?
>
> On Sep 12, 2009, at 8:46 AM, Someone Something wrote:
>
>> But, I'm returning true or false right?
>>
>> On Sat, Sep 12, 2009 at 11:32 AM, MRAB <python at mrabarnett.plus.com> 
>> wrote:
>> Someone Something wrote:
>> Project euler (in case you don't know: projecteuler.net 
>> <http://projecteuler.net>)
>>
>>
>> I'm trying to do the third one and here's my current code:
>>
>>  1 def checkPrime (x):
>>  2     factors=2;
>>  3     while factors<=x:
>>  4         if x==factors:
>>  5             return True;
>>  6         elif x%factors==0:
>>  7             return False;
>>  8         elif x%factors!=0:
>>  9             factors=factors+1;
>>
>> You're not returning 'factors', so the function will return None.
>>
>>
>>  10
>>  11 factorl=[];
>>  12 factors=600851475142;
>>  13
>>  14 while factors != 1:
>>  15     if 600851475143%factors==0:
>>  16         if checkPrime(factors)==True:
>>  17             print factors;
>>  18         else:
>>  19             factors=factors-1;
>>  20
>>  21     else:
>>  22         factors=factors-1;
>>  23
>>
>> And it just gets frozen when I run it. I put a
>>
>> print "Loop completed"
>>
>> in one of the loops and it showed up just fine. So, there are two 
>> possibilities:
>> 1. Its looping in the trillions and taking a while
>> 2. I have a forever loop somewhere
>>
>>
>> -- 
>> http://mail.python.org/mailman/listinfo/python-list
>>
>> -- 
>> http://mail.python.org/mailman/listinfo/python-list
>
It's a rather minor point that it returns None for values less than 2.  
If/when somebody writes documentation, one might just specify the 
precondition that x >=2.  After all, there aren't too many primes below 
that value.  And actually, when one does an if-test, None is pretty 
close to False.  And this program won't call it with a value less than 2.

To the OP:

The original Euler problem asked   "What is the largest prime factor of 
the number 600851475143 "

This program could get that answer, but very slowly.  The problem is 
it's starting its guessing at 600 billion, and counting down by ones.  
That's going to take a very long time.  The OP needs to study the nature 
of factoring, to pick a better starting point.  There are other 
inefficiencies, but this one fix gets the run time down to a couple of 
seconds (if you don't count the fact that it then repeatedly prints the 
answer, ad-infinitum.)

Another piece of advice - pick symbol names that represent their purpose 
in some way.  An integer shouldn't be called factors, since that's 
plural.  When I see a name like that, I expect to see a list of integers.

Please don't include line numbers;  it makes it quite difficult to 
copy/paste the code into an editor to try it.  And lose the semicolons.  
They're a leftover from other languages.

DaveA