[Tutor] making lists of prime numbers

[Dave Angel]

On 09/14/2011 10:35 PM, Andre Engels wrote:
> On Thu, Sep 15, 2011 at 4:01 AM, c smith<illusiontechniques at gmail.com>wrote:
>
>> hi list, i am trying the MIT opencourseware assignments.
>> one was to find the 1000th prime.
>> since this isn't actually my homework, I modified the solution as I would
>> like to collect lists of primes and non-primes up to N, also some log()
>> ratio to one comparison.
>> here is what I came up with on paper:
>> #!/usr/bin/env python
>> import sys, os, math
>>
>> def main(a):
>>      notprime = []
>>      primelist = [2,3]
>>      nprime = sys.argv[1]
>>      numcheck = 4
>>      while len(primelist)<  nprime:
>>          for i in range(2,numcheck-1):
>>              if numcheck % i == 0:
>>                  print numcheck,'is not prime'
>>                  notprime.append(numcheck)
>>                  numcheck += 1
>>                  break
>>              if i == numcheck and numcheck % i !=0:
>>                  print numcheck, 'is prime'
>>                  primelist.append(numcheck)
>>                  numcheck += 1
>>                  break
>>      TwotoN = 0
>>      for j in primelist:
>>          TwotoN += log(j)
>>      print 'sum of logs of primes from 2 to', nprime,'is',TwotoN
>>      print 'the ratio of this sum to 1 is' %f % (float(TwotoN)/nprime)
>> if __name__=='__main__':
>>      main(sys.argv[1])
>>
>> my questions would be:
>> am I passing arguments from the command line correctly?
>> this seems to count by twos (going through both 'if statements' maybe?)
>> I thought the 'break' would send control back to the 'while'
>> basically, is there an obvious problem here or is it just completely wrong?
>>
> I'd say the obvious problem is your second if statement. Its guard will
> never be true. i goes through range(2,numcheck-1). The highest number in
> that range in numcheck-2, so i==numcheck will never be true. Even if you'd
> get i to equal numcheck somehow, numcheck % i would then ber equal to
> numcheck % numcheck, which equals 0, so numcheck % i != 0 would not be true.
>
> The obvious thing to do seems to be to get this code out of the for loop,
> without and if statement guarding it.
>
> Another thing that goes wrong is:
>
> nprime = sys.argv[1]
>
> You use nprime as an integer, but sys.argv[1] is a string. You should thus
> change this into
>
> nprime = int(sys.argv[1])
>
> However, for the sake of reusability, it's better to have a function that
> gets the first n primes for n decided by the caller than to have a function
> that gets the first n primes for n always being the first argument, thus I
> would change it to:
>
> nprime = int(a)
>
As  Andre and Alan have said, there are some problems with your code.  
However, the basic concept is reasonable.  I wouldn't worry much about 
efficiency, yet.  Get it to work reliably, then figure how to tune it.  
And if you have a source control system (like git, svn, mercurial), 
check in each version that works, so you can always compare to what you 
currently have.

Your specific questions:
   1) you're passing the (one) argument from the command line 
reasonably, though I'd convert it to int before passing it, and I'd 
change the formal parameter name of it in your function to nprime.  Then 
you don't need any additional assignment in the function.
   2) it seems to count by twos because of the problems with your second 
if, as Andre has said.

Start by fixing the second if statement.  There are two ways to fix it.
     a) change the condition so it detects the end of the loop, which in 
your case is numcheck-2.  Catch to that is that when you realize you can 
optimize the loop, you'll have to remember to change the if to match.
     b) move the code outside of the loop.  However, you'd also have to 
make sure it *didn't* get executed if the first if statement did.  That 
could be a real pain, except that Python has a nice "else" clause you 
can attach to a loop, that only gets executed if the loop completes 
normally.  That else is exactly what you want, so it makes it 
straightforward.

Once you see it generating the correct primes, you may notice that it 
sails right past the nprimes value.  That'll get fixed when you add the 
int() function when calling main().  Comparing int to string usually 
doesn't do what you'd want.

next problem you'll have is the log function, which is defined in math.  
So you want to call math.log()

next problem is the misplaced quotes on the last print statement.  
You'll get an error when you hit that one.

Finally, the wording of those two prints is all wrong, so you might want 
to fix it so it matches what the code does.

HTH


-- 

DaveA