[Tutor] Making a Primary Number List generator

[Dave Angel]

(Please don't top-post.  And don't reply privately, as I'm not the only 
one reading this thread.  Post the reply to the list, as you did last 
time with your reply-all)

On 05/13/2013 09:45 PM, Daniel Magruder wrote:
> Dear Dave,
>
>> I don't have a clue what you're confused about.  Do you not understand remainders?  If the remainder is 1 then the number is odd, while if the remainder is 0 then the number is even.  That's math, not programming.
>>
> I understand remainders, I am confused with some of the innate functions of python, such as what it assumes. For example here is my code, and maybe this well help explain where I am confused...
>
> def isprime(x): # this is a function to find out if a number, x, is prime
>      test=2 # this number will test to see if x is prime by exhaustive division
>      numberinquestion = x
>      while test < numberinquestion: # so long as test is less than the number I am testing, then I will compute the following block
>          if numberinquestion % test == 0: # if the the remainder is zero then the number is not prime
>              test += 1 # I am increasing test by one to make sure I exhaustively go through all the numbers
>             # between test and x

Well that increment is misplaced, since you're about to return,  Who 
cares what test is since it's discarded upon function returning?

  I am unsure if the while loop would automatically increase test
if I did not specify +=1. While 6%5 gives a remainder, 15% 5 does not, 
but 15%6 does.

If just one case has no remainder, you've found a non-prime and you can 
return.  Who cares if some of the others have remainders?

>              return False # if this condition is met, then the number is not prime.  How do i know that false is assigned to x not test?

It's False, not false, and it's not assigned to any local variables. 
It's returned.  So in your case, the caller is testing it for True, 
since the caller is in an if test.  The caller will then skip his 
append(), and the value won't be added to the list.

At this point, you're missing the other increment of test.  This is 
where the    test += 1 is needed.

>      return True # I am unsure why this works, does it only get to this point after going through the while, so test = x?

Yes.

  How do I know that this works?

That's the definition of a while loop.  it won't fall out of the loop as 
long as the condition is true.  So at this point, we can be sure that 
test is not less than numberinquestion.  Since it was incremented by 
only 1 each time, it must be equal to numberinquestion.

I mean, couldn't the interpreter go through the while and then assign 
true to a non-prime number?

No, because if the number was non-prime then one of the numberinquestion 
%test  would have been zero, and we would already have returned from the 
function without getting to this line.

  Also, since before this is an if statement, that means if x % test != 
0 then it automatically

No idea what you mean by "it" in this question.  Nowhere is there an 
assignment to True in this function.  Returning False does not assign 
anything, and it also ends the function.

> is assigned to true, even if the test number is 4 and x is 15. So wouldn't this not go to 5 and find the remainder? How do I know this will continue to test every possibility?  HERE IS MY CONFUSION.
>

When x is 15, it has already exited before it gets to 4.  So let's 
pretend you're asking about x being 25.

when test is 4 and x is 25, it will skip the return False, increment 
test (once you move that line), and go back to the while statement. 
That time around it will find a zero remainder, and return False.
>
> def counting_primes(): # a function to create a list of primes
>      prime = 2 # two is the first prime and can problematic so starting at two
>      primelist=[] # I want to start with an empty list
>      while len(primelist) < 1000: # I want a list with 1000 items in it, so to do that, I will use while the length is less than 1000
>          if isprime(prime): # conditional calling is prime function
>              primelist.append(prime) # appending the variable prime to primelist if the value is true, but I am worried if this will give false positives based on my previous comments above

No, by definition, you trust the function above. If it's broken, fix it, 
don't worry about it here.

>          prime += 1 # check the next number to see if it is prime
>      return primelist # still not totally sure what return is doing, it doesn't print, so is it the same as primelist = primelist? is it reassigning my empty primelist at the start of the function to what ever it is now at the end of the conditional?
>>
>> Here you go again;  int is a type, not a value.
> I was thinking that if you do something like 15%4, there is a remainder 3 which is an int, and as primes got excessively large that ==0 may not be enough to recognize primes that are (except two) odd

You can't explain a return without mentioning the caller, and you've 
removed the caller from this code.  Return passes the value directly 
back to the caller of the function.

#top-level code:
myprimes = counting_primes()
print myprimes[7]

   If that caller assigns it to a variable  myprimes then you have (in 
effect)   myprimes = primelist.  It does not print it.  But the 
top-level code can then use the returned value any way it likes.


Modulo will work accurately for int and long up to the point where you 
run out of memory, which will be typically for a number hundreds of 
millions of digits long.  You're thinking of floats, which are 
inherently flawed for this type of work.

>>
>>
>>>              test += 1
>>>              return False

>>>      if test == numberinquestion:
>>
>> This is also unneeded.  If the while has finished, then you can return True.
> Yeah I guess your write that is unneeded, but I wasn't sure if after the first if conditional test would return to 2??
>

Only if you had the prime = 2 inside the while loop.

>
> So does this clarify why I do not understand this? Also, that code above, I tried it and it did not work, it gave a general syntax error...
> Sincerely,
> Dan
>
>

That gives me no clue to help you with.  A syntax error points to a 
particular line, and column within that line.  Sometimes the actual 
error is in the previous line, but that does narrow it down quite a lot.

So when you say it gives an error, show the full traceback.

def isprime(x): # this is a function to find out if a number, x, is prime
     test=2 # this number will test to see if x is prime by exhaustive 
division
     numberinquestion = x
     while test < numberinquestion: # so long as test is less than the 
number I am testing, then I will compute the following block
         if numberinquestion % test == 0: # if the the remainder is zero 
then the number is not prime
             return False # if this condition is met, then the number is 
not prime.
	test += 1
     return True # It made it all the way, and had nonzero remainders 
everywhere


def counting_primes(): # a function to create a list of primes
     prime = 2 # two is the first prime and can problematic so starting 
at two
     primelist=[] # I want to start with an empty list
     while len(primelist) < 1000: # I want a list with 1000 items in it
         if isprime(prime): # conditionally execute next line based on 
isprime() return value
             primelist.append(prime) # appending the variable prime to 
primelist if the value is true
         prime += 1 # get ready to check the next number
     return primelist # still not totally sure what return is doing, it 
doesn't print, so is it the


myprimes = counting_primes()
print len(myprimes)
print myprimes[:10]

This code is not the way I would write it, but it follows your original 
logic, and works.  Only once you understand why it works should you try 
to optimize it.

--
DaveA