Question

Could someone give me a pointer on the following code? (ps1a)
count =1
numberoftest = 3
max_count = int(raw_input("How many prime's would you like to find? "))
while count<=max_count:
for x in range (1,numberoftest):
if numberoftest%x==0:
numberoftest = numberoftest+1
break
else:
numberoftest = numberoftest+1
count = count+1
print "prime", numberoftest

Sorry there are no comments but for some reason they weren't "pasting" in... I've come at this problem different ways and here is the latest but I'm not getting anything out.

Answer 1

Hello MPizzie,

One problem I notice about your program is your for loop:

for x in range (1,numberoftest):
if numberoftest%x==0:
numberoftest = numberoftest+1
break
else:
numberoftest = numberoftest+1
count = count+1

Assuming your "else:" clause is indented correctly in your file, numberoftest%x when x = 1 will always yield 0. So your if statement will never catch any prime numbers- all numbers are divisible by 1. Try range(2, numberoftest): instead.

Answer 2

Can you post your code to codepad.org with your comments? It would make analyzing it much easier for everyone.

From just looking at it...well lee832 beat me. Your test for primes needs to be redone.

Answer 3

done : http://codepad.org/OQVhkrzt
that's a pretty sweet site...

Answer 4

not sure how much the comments will help. I'm beginning to think that part of my problem is my math being rusty...

Answer 5

thanks lee... I actually caught that just prior and reran it. What I get now is a list of consecutive numbers that stop seemingly randomly

Answer 6

This problem is much much easier if you approach it as a series of functions.

So first, we take a function that tests for prime http://codepad.org/E4zlGWNC (this is an adjustment of your code)

And then we call that function in a new function that iterates through a range and produces the last number tested. Trying to do this problem as a nested loop is difficult. Sorry I can't be more helpful, but take a look at the code I posted and try and work with that.

Answer 7

well, you need to have two loops: one for prime candidates and one for divisors and you should be doing something like:
while the number of primes found is less than desired
using all the numbers between 2 and the prime candidate
test the prime candidate for primeness
if it is not prime stop testing
if it is prime increment the number of primes found
get the next prime candidate

Answer 8

First, only write the inner loop that tests a single number for primeness. Only when you get that working should you worry about the outer loop. Your inner loop isn't working.

Answer 9

Great help guys! Seanlerner...looking at the problem as a set of functions helped as i think I was just trying to do too much at the same time. I've finished it and it works although because of the number's I'm using I'm missing the first prime "2". Any sugestions? http://codepad.org/iG71sgjb

Answer 10

dmancine-
is that the easiest way to look at it? From the inside out? I'm thinking it's easiest to start on the smallest pieces and build from there...is that what you're doing?

Answer 11

Yes. The outer loop is counting primes. The inner loop is determining what's prime. You can't count primes until you can reliably find them.

There have been a LOT of questions in the past week about this very problem. And all the code that has been posted has the same form: both loops are there, and the inner loop doesn't work. It's possible to debug the nested loops when neither is working, but it's super hard, especially for beginners. It's much easier to start by writing code that is easy to get right, then build on it incrementally. Then you know the program is working after each step, so you'll never need to debug it.

The main thing that complicates this problem is that you haven't been shown how to write a function yet, so you're not supposed to use functions in your solution. I think they did that on purpose. Writing a function, isPrime(n), would make the problem much easier to solve. But they're trying to get you to build a complicated program incrementally. So, write code that finds a prime, then wrap that code in some code that uses it.

In a later problem set they're going to ask you to find the largest number of McNuggets that can't be bought using boxes of 6, 9, and 20. But that relies on being able to tell if you can buy n McNuggets using boxes of 6, 9, and 20. Writing the test is not trivial. Neither is solving the main problem. If you try to write the code to do both parts all in one go, you're doomed.

Answer 12

You don't find 2 because you never test it. You start numberoftest at 3.

The easiest way to fix it is to start numberoftest at 2, and increment numberoftest by 1 at the end of each loop. Yes, it's less efficient, but not by much. Every even number will fail the isPrime() test on the very first divisor.

A note regarding code. What does this code do:

if test:
x += 1
else:
x += 1

Now apply that to where you increment numberoftest.

Also, you're using your function a little weird. You're defining it every time through the loop. You can move it outside of the loop. But what you're probably supposed to do is not use a function. Try putting that code inline right where you have it, and setting a variable instead of returning a value. I think that's the point of this problem (since they haven't covered functions by this point in class).

Answer 13

Thanks for all the advice. I'll try without the function as well (as you suggested) as learning as much as possible is definitely key for me. I was grasping as I didn't want to loose two more hours to a blank screen. ;) Also, thanks for the +=. Not sure where that came from and I feel like I'm missing something (handouts maybe) but that should make it cleaner.

Answer 14

Below the lectures there is a box with tabs. One says "Related Resources." There you'll find links to the handouts and transcript for that lecture.

Another thing I didn't find until far into the class is the readings. On the left side of the page there is a sidebar with links to Readings. Those would have helped a lot.

But the thing that will help most in this first problem set, even more than the readings or handouts, and I can't stress this enough, is solving the small problem first before attempting the big problem. It's even worth throwing away the work you did and starting over. A clear screen is a clear mind.

Something psychology has found is that humans can keep track of 7 plus or minus 2 chunks of data. In a program, each variable is a chunk of data. So if you're writing a program that is manipulating 7 variables at once you're almost sure to get something wrong. Even if you get it right, at the very least, it will be very hard to keep everything straight. So programmers use functions and classes to break large operations into smaller ones that are easier to understand and implement. If we could write an isPrime() function for this problem, that would convert probably 3 of the variables into one function call. But we can't. So we have to write that function in-line first, and get those 3 variables squared away, THEN introduce the 3 or 4 other variables needed to count the primes. If you can, don't test that 5-chunk lower bound.

If I had written this problem set, I would have broken these steps into two separate problems. It's too much for beginning programmers to ask them to come up with this deconstruction of the problem. Or at least give a huge hint to write the inner loop first and get that working well before doing the outer loop.

Answer 15

Oh, and what I was getting at wasn't the += operator. I was trying to say that if you're doing something in an if and else case, you're always doing it, so you can pull it out of both cases and put it at the end.

if test:
x += 1
else:
x += 1
y += 1

becomes

if !test:
y += 1
x += 1

The second version is easier to read. Try to understand why these are both the same thing. Then apply it to the if/else you posted.

Answer 16

alright, it's a new day. here's where I'm at... I seem to be able to get a program that finds primes fine. Hard to know for sure since I have to plug each one in individually but the number's I've tested seem to work: http://codepad.org/YQtCG0Aw

The problem I'm having is when I try to include that code into a greater loop that would give me a number of primes requested. I am trying to increment my num (the one that's tested) each time the inner loop (the one above) makes a decision about the number being prime. I seem to be incrememting the base and num at the same time so I keep getting 2,3,4,5,6...for example if 5 prime's were requested... I've moved indentations around and tried adjusting where I put things and I can't figure it out. Should be a simple thing but the #1 things I've realized from this problem set is just HOW AMAZINGLY PRECISE AND LITERAL everything must be placed. Craziness. Here's the full code: http://codepad.org/DQPvHeCw

Again...trouble seems to be when putting the inner loop in the outer loop... IDK. Going to step away for a bit. I will say that I've alreadly learned so much from trying different versions to get this problem right. Coding is a fickle thing. Sure can't wait to speak fluently. :) Thanks guys (and/or girls).

Answer 17

not flutterle
*read fickle

Answer 18

lol...does it not like -fickle-?

Answer 19

The site doesn't allow fluttering swearing...

Answer 20

also, here is your code set to search for the 7th prime (easier to see what it i doing since codepad doesn't allow input): http://codepad.org/eold2umN

Answer 21

good point seanlerner, thanks. I promise I was only trying to spell elkcif frontwards. ;)

Answer 22

First, THANK YOU for writing just the inner loop and posting your code! Could you see how it was easier to just solve that problem, and not have to worry about the bigger problem? Also, you have working code for the inner loop, and it's posted online, so if you mess something up when you do the next step you can look back at what was working before. And now you can concentrate on just the outer loop, relying on the inner loop just working (if you don't mess it up, that is ;) ).

First, you had a break statement in your original working loop that seems to have disappeared. That's definitely going to affect behavior.

Second, when you wrapped the existing code in another loop, you didn't quite get everything. You need to re-initialize the inner loop variables on each trip through the outer loop. What variables are you neglecting to reset?

The last thing is actually a bug. You're only updating num when you find a prime.

Answer 23

YESSSSS!!! Wow does it feel good and wow was it a learning experience. "where to break, where to increase the count, where to indent certain parts...?" It was definitely worth working through. Thanks everyone. Dmancine...that last post had the final clues. Thank you so much for all the suggestions and nudges in the right direction... Here it is: http://codepad.org/I17u2q1O The 1000th prime = 7919 Man I hope they get easier...