yes, im still stuck on that primes problem. my code is this: http://dpaste.com/532787/
my bug begins after the 24th prime. for the 25th i get 95 and not 97. since my tuple contains all the #'s from 2 up to but not including the value being tested, and 95%5==0 is true, it should add 2 to the number again, but it doesn't. when i try running the for loop 999 time it gives me the 800 something th prime. i just can't seem to figure our the bug. my (tiny) brain has ben struggling with this problem for a tremendous amount of time. help.....

- anonymous

- Stacey Warren - Expert brainly.com

Hey! We 've verified this expert answer for you, click below to unlock the details :)

- katieb

I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!

- anonymous

I couldn't really just find a single bug or an easy fix for your code so I kind of just rewrote it for you if you have any questions just ask. http://dpaste.com/hold/532804/

- anonymous

Double_o, your outer loop is only iterating 49 times, and your inner most one is making your divisor search skip a lot of possible divisors for some of the prime numbers. I think inserting a few print statements would make it pretty obvious where things are going wrong. Just put a line in a few different places to show where you are in the code and what the values of prime, div, and i are.

- anonymous

sry i was using 49 to see if it would give me the 50th prime and forgot to fix it. but what do you mean that its skipping possible divisors? doesn't the range give the values from 2 up to but not including the upper value in range? sry im really slow sometimes

Looking for something else?

Not the answer you are looking for? Search for more explanations.

## More answers

- anonymous

Yes, the range(2,prime) will give a list of numbers from 2 to prime, but inside that you're incrementing your prime variable and continuing to look for divisors from the list for the original prime, not the newly incremented one.

- anonymous

ok, so your saying that the prime value in range(2, prime) is 3 throughout the entire loop?

- anonymous

polpak had a good idea:
try this out, http://dpaste.com/533072/
i put a few print statements in there - makes for a long listing but you can see that is actually "going wrong" a lot earlier even though it provides correct results - stop it from running with ctrl-c then scroll back to examine the output
Heres a good example i=8 and prime = 25.
http://dpaste.com/533073/
sometimes inside your while loop you change the number you are testing for primeness but div just keeps incrementing - it never goes back to check the 'new prime' for the lesser values of div. later on that might lead to problems.
print statements rule!!
was that while loop an attempt to optimize?
optimization early to the dark side leads

- anonymous

AH! the light just turned! on now i see what it is doing. thank you all for your help. now that i understand what it is doing wrong i might be able to fix it (hopefully)

- anonymous

- anonymous

here's my updated code: http://dpaste.com/533273/ i added to more for loops so that it would update the upper end of the range. since it was able to give me the ten-thousandth prime correctly, im thinking that its ok for the purposes of this lesson. any comments? thanks polpak and bwCA

- anonymous

me personally, i would not change two things inside of loops.
because you are doing this you have to have multiple nested loops to go back and account for those changes which complicates the program and makes it hard to understand what's going on.
check out the zen of python:
http://www.python.org/dev/peps/pep-0020/
bottom line - if you get the right answers, you get the right answers. the purpose of the course is to learn how to think like a computer scientist and learning python is a side benefit (big one imo). the way you implemented this may work for a simple/small problem like primes but if you use that approach for larger/complex problems it might get real ugly. the caveat here is that i really don't have a lot of experience but i have written some ugly programs - that's why i'm taking the course. as the code gets more complicated, you should add more comments to explain what it is doing so that when you look at it next week you can figure out what it's doing.
if You(!) think your code is starting to get ugly it might be time to regroup and rethink the solution. I can tell when this is happening to me when i keep having to go back and add all kinds of stuff to just MAKE IT grind away at a problem till it works.
in this case, i would have an outer loop that changes prime and an inner loop that changes div. just my take tho - maybe someone else will jump in..

- anonymous

thanks for the advice

- anonymous

One of the things to start thinking about is Given some large problem, how can I decompose into a set of smaller problems. For this case, you need to find a bunch of prime numbers. To do that, you have to move through the set of potential primes, and test for primeness.
So it breaks down into two smaller problems. Problem (1) move through the set of potential primes until we have found 1000 primes. Problem (2) test a given number to determine whether or not it is a prime.
The solution to the first problem relies on the solution to the second, so start with the second problem first. If I give you a number testNum = 53982717637291, can you write a small bit of code that will determine if testNum is a prime number?

- anonymous

well, you could take one of two approaches
1. divide by all numbers except 1 and the number u mentioned is prime. if there's no remainder for any of the numbers, then it is prime
2. check to see if any of the previous primes divide evenly into the number. if they do not, then the number is prime
thats what immediately comes to mind

- anonymous

But for the example I gave, you don't have any previous primes.

- anonymous

then the only option is 1, but i don't think its a good method. honestly though, i can't see another way

- anonymous

it would be like i did in my program where:
for i in range(2, #):
if # % i == 0:
print "# is prime"
else:
print " # is not prime"

- anonymous

opps i got that backwards
for i in range (2, #):
if # % i == 0:
print "# is not prime"
else:
print "# is prime"

- anonymous

That won't quite work right. First use testNum instead of # and imagine that testNum = 15. What will this code output?

- anonymous

oh i didn't think that that would happen.......

- anonymous

Can you correct the problem?

- anonymous

i tried this:
testnum = 15
for i in range(2, testnum):
if testnum % i == 0:
testnum = 2
else:
testnum = 0
if testnum <3 and testnum >1:
print "not prime"
else:
print "prime"
but its not correct because it testnum = 100 it still says prime... :(

- anonymous

Ok, lets take a step away from the code. Describe in english what you would do to determine if 15 was a prime number?

- anonymous

wait, i just had a thought

- anonymous

you could find the divisors to testnum and see if any of them are prime

- anonymous

Does it matter? If you find a divisor for testNum it is definitely not prime unless it's 1 or testNum.

- anonymous

Let me describe a process to you, and you tell me what you think.
Loop for every number from 2 to testNum-1.
If that number divides testnum, testnum is not prime
If we get to the end before we found a divisor testnum is prime

- anonymous

Actually I don't like the word loop in that explanation, but oh well.

- anonymous

Does that process seem as though it does what we want?

- anonymous

sounds right to me.....

- anonymous

#Ok so you have the outer part down
for i in range(2, testNum):
#And also the part where we check if i divides testNum
if testNum % i == 0:
# What should we do here??

- anonymous

i'd like to say that it's not prime, but i did that i nmy last cade and it didn't work so i'm kinda lost

- anonymous

Well you're right. We can say it's not prime. But what else do we need to do?

- anonymous

Should we continue searching?

- anonymous

we need to kill the program

- anonymous

We need to end the loop. Do you know of a way to end a loop early?

- anonymous

sadly, no

- anonymous

Ok then. Do you know how to write a while loop?

- anonymous

since ive only watched up to lesson 3 i only know about for loops

- anonymous

Ok then. Lets try this. Can we safely assume that a number is prime unless we find something showing it is not prime?

- anonymous

oh wait u mean the "while something is true, do something" loop?

- anonymous

Yes. That is a while loop.

- anonymous

ooooooooooh ok then i guess ive seen it before

- anonymous

Can you write a while loop that is the equivalent to
for i in range(2, testNum):

- anonymous

div = 2
while div < testnum and div >= 2:
testnum % div # im still not quite whether to bind it to something, set it equal to something or something else so for the time being, i'll leave this portion incomplete
div = div + 1

- anonymous

do i need an if clause in there?

- anonymous

No, that's great.

- anonymous

One minor point (doesn't matter much) since div = 2 and you're adding to it inside the loop it will never be < 2. So the div >= 2 bit isn't needed.

- anonymous

So
for div in range(2, testNum):
is the same as
div = 2
while div < testNum:
div = div+1

- anonymous

never thought until today

- anonymous

never thought about that until today*

- anonymous

wait, since all the numbers being tested are odd, couldn't we set div = 1 in the beginning then increment it by 2 to get it to divide by all odd numbers, since no odd number is evenly divisible by an even one?

- anonymous

Sure, that'd save us some bad tests certainly.

- anonymous

no that won't work we have to set it to 3 since it would evenly divide by 1

- anonymous

Yeah good point.

- anonymous

But still, that's a decent optimization.

- anonymous

Ok, so now did you decide if it would be ok to assume that until we find a number which divides testnum, we can assume it is prime.

- anonymous

yes i would think so

- anonymous

We are trying to tell if testNum is prime because we plan to do something with that piece of information. So perhaps we should have a variable to keep track of that info. Something to indicate the 'primeness' of testNum so once we determine it, we don't have to test it again.

- anonymous

What should we call that?

- anonymous

are you suggesting to store the prime values in a tuple?

- anonymous

No. I'm saying have a variable 'testNum_is_prime' or something that is True if testNum is prime, and False if it is not prime.

- anonymous

im not sure i understand what you mean by storing and not testing again.

- anonymous

Well, we are looping over all the divisors right? And when we find one that divides testNum we know at that moment testNum is not prime. But after that moment is passed, how will we know? Once we've finished the loop, what can we do to see if we made it through successfully without finding a divisor or not?

- anonymous

If we store that knowledge somewhere we can retrieve it later

- anonymous

we could say something like prime = testnum if testnum is prime and not_prime if testnum is not prime

- anonymous

Sure. But we only know testnum is prime if we make it through EVERY divisor and don't find one that works. We know it is not prime if we find just 1 that works.

- anonymous

So really we just need to know if it's not prime. Perhaps we can call the variable notPrime.
if testNum % div == 0:
notPrime = True

- anonymous

but we can't assign to literal right?

- anonymous

notPrime is just a variable name, like testNum or div

- anonymous

i meant we can't assign a variable to something literal, but i found out we can call it true so never mind

- anonymous

True is the universal truth object in python. Just like 1 is the universal unary object.

- anonymous

So it's ok. If you prefer though you can do something like
notPrime = 1

- anonymous

sry i didn't know that

- anonymous

So now we have our loop:
div = 2
notPrime = 0 # We don't know so we assume it's prime
while div < testNum:
if testNum % div:
notPrime = 1
if notPrime == 0:
print testNum, "is prime"
else:
print testNum, "is not prime"

- anonymous

Whoops, I'm missing a few things.

- anonymous

I forgot to increment div, and you wanted to start div at 3 instead of 2. Can you fix it?

- anonymous

Did I lose ya?

- anonymous

- anonymous

not yet :)
http://dpaste.com/533358/

- anonymous

Great except that the div = div+2 bit needs to not be part of the if block right? We always want to increment div

- anonymous

http://dpaste.com/533360/

- anonymous

right

- anonymous

Ok, now that should work well. Can you see any way we can optimize it further?

- anonymous

Oh, actually your version has a minor bug.

- anonymous

if testNum % div:

- anonymous

testNum % div will be True when?

- anonymous

testNum % div == 0

- anonymous

right. Otherwise it would do the opposite of what we want since 0 evaluates to False in a boolean context.

- anonymous

oh ok sry about that

- anonymous

but now i need to modify the program so that it will generate numbers, test to see if they are prime, then spit out the 1000th prime number right?

- anonymous

Certainly! But we already have some code to test for primeness, so all we have to do is take this code we have, and nest it inside some other loop that changes the value of testNum.

- anonymous

so we could basically set testNum = 1 in the begnning , loop it to the desired prime-1, then keep testing the odd numbers?

- anonymous

Well you want the 1000th prime, so you need to keep a count of how many primes you find.

- anonymous

oh yeah....

- anonymous

do we use a tuple then?

- anonymous

or range (1000)

- anonymous

No, just a variable.
testNum=3
primeCounter = 1 # Since we're skipping 2
while primeCounter < 1000:
...
testNum = testNum + 2

- anonymous

oh duh

- anonymous

Then when you find a prime (in addition to printing it) you can increment primeCounter.

- anonymous

the ... is where our original code will go.

- anonymous

with nearly no modification

- anonymous

so if i basically stick all this together i can get any prime i need so long as i make primeCounter < anyVariable and have anyVariable = input("some sort of blah")?

- anonymous

Yes essentially.

- anonymous

It will take longer, the farther you go because of the increased sparsity of primes

- anonymous

But it will work

- anonymous

thanks for all your help. now i think i see what i was supposed to. your a lifesaver

- anonymous

of course!

- anonymous

i'll be back when i need more help but thanks in advance :D

Looking for something else?

Not the answer you are looking for? Search for more explanations.