Question

Ok guys....I needs some help. After toiling with this for the last week(i estimate 10 -15 man hours) I've finally met a point where I need to ask for help. I'm working on PS 2. Counting primes. I've gone through various methods...found a point where I could get all the odds, then was trying to filter out only the primes, etc etc. I'm currently following the suggested method....so here it is:

"check my next post...as the script won't fit here"

Answer 1

Which I've now changed to:

oddslist = []
primeslist = []
x = 2
primen = 0

while primen <= 1000 :
if (x % 2) != 0 :
oddslist.append(x)
print x, ' is odd'
for y in oddslist:
if x % y != 0 :
primeslist.append(x)
primen = primen + 1
else:
x += 1

else: x = x + 1

print primeslist

Answer 2

I put your code on codepad so it's easier to modify and run.
http://codepad.org/hHEWQZXS

Your code doesn't detect primes correctly. Start by just writing the code that detects if a single number is prime. Ignore the task of having to find many primes. Only when you can reliably determine if a number is prime or not should you try to find multiple primes.

Answer 3

I appreciate your reply dmancine, i've included my defined 'ifprime(x)' function. here: http://codepad.org/O8FqiVcy

I can't manage around it...it appears its always in a neverending loop. Help me with something:

1. need variables CHECK
2. need to initialize loop: (while y < x) Right?
3. function: (if x % y != 0) right????
4. block of code(loop) : y = y + 1
5. terminate: print


I even went about trying to do a FOR loop by saying : for y in range(2, z): (where z = x -1)...to no avail

I seem to be missing something conceptually with programming. Do you or anyone else have an analogy for me to understand this process better? Or at the very least point out whats wrong in my code. Thanks all

Answer 4

First thing's first. ifprime(x) then what? A function that should return a boolean should be named after an assertion, like isPrime(x).

Second, you listed 5 steps in your response, but you don't actually know if you've gotten any of them right. Start with step 1, write code to do that one step, then test it. You test it by adding a print statement to your code, printing out some variables (and maybe some helpful text, like the name of the variable), and visually inspecting each line of output to make sure it's exactly what you expect.

But before doing that, first explain exactly how you want to determine if a number is prime or composite. If it helps, think about specific numbers, like 10 and 11. Those are large enough to be meaningful, but small enough to be done by hand.

Answer 5

Ok D, lead me along some more if you please. I believe I've created a working script for isPrime(x)....see here: http://codepad.org/Yz5RlcVT .

And I'm able to generate a list of odd numbers .....see here: http://codepad.org/HtzTam56

but when I try to run isPrime on the oddslist...something goes haywire. see here: http://codepad.org/6fh41fXN . As you can see I've tried to implement the MAP function, to no avail. Also I tried another method down below(commented out) but that just seems to put the first variable into a loop. What am I not getting? Or how do I properly assert isPrime into a list? Thank you for you help, its much needed :)

Answer 6

Very good. You are detecting primes reliably. I'd probably take the print statements out of the function so you don't get all the debug output. The return value is all you need to know if the argument is prime. (Also, the function should really return True or False, not 0 or 1.)

http://docs.python.org/library/functions.html#map is the description of the map() function. What does it return? What are you assuming it returns? Also, I think you're probably thinking it works like filter(), which it doesn't. Look up the filter() function on the same page.

Before you go too far down the filter() road, filter takes a list (or sequence) of items to filter. But that sequence needs to have well-defined beginning and ending points. What will you use for the end point? You won't know how big the 1000th prime is until you find it. But by using filter() you can't find it until you know it. If you already know it, then why find it? Catch-22. You should come up with a way to keep searching forever, until you find 1000 (or some other number) primes.

If you get confused, then start by writing a loop that finds 1000 (or some other count) primes, but assume that every number to get is prime. Don't call your isPrime() function. Just make sure you loop over the right numbers, starting at the right number, finding the correct count of items, and stopping at the right number. Print out what you do at each step, and verify that what you print is what you expect. It will be much easier to start with a number smaller that 1000, like 10. But also test 1 and 0.

Once you get that working reliably it should probably be easy to put the prime test back in. But don't worry about that until you get the loop working as I described.

Answer 7

My bad. Yes, you're use of map() is wrong, as I'm sure you'll realize when you read the documentation of map() and filter().

Your commented-out code is pretty close. I don't know what you mean by "first variable" but what is x in that code? What is it supposed to be and how are you actually using it? Also, you can assign the return value of isPrime() to a variable, then test that in your if and else conditions.

Okay, here is a style lesson.
if isPrime(x) == 1:
primeslist.append(x)
primeN = primeN + 1
x += 1
elif isPrime(x) == 0:
x += 1

Change that to
xIsPrime = isPrime(x)
if xIsPrime == 1:
primeslist.append(x)
primeN = primeN + 1
x += 1
elif xIsPrime == 0:
x += 1
That way you only run the (expensive) prime test once per x.

You know isPrime() only returns 0 or 1, so if isPrime() didn't return 1, then you know it returned 0.
xIsPrime = isPrime(x)
if xIsPrime == 1:
primeslist.append(x)
primeN = primeN + 1
x += 1
else:
x += 1
This would (hopefully) be even clearer if isPrime() returned a boolean.

Look at the last lines of your if and else blocks. When they're the same you can do this:
xIsPrime = isPrime(x)
if xIsPrime == 1:
primeslist.append(x)
primeN = primeN + 1
x += 1
You end up doing the same thing whether xIsPrime is 1 or 0.

Finally, since you got rid of the second test you can get rid of the temporary variable.
if isPrime(x) == 1:
primeslist.append(x)
primeN = primeN + 1
x += 1

And when you change isPrime() to return a boolean DON'T compare the return value to True or False. A boolean value is already a condition.
if isPrime(x):
primeslist.append(x)
primeN = primeN + 1
x += 1

And, having said all this, there's still a bug in that code. Also, it's looping over that finite list, which won't work when you don't know how big the 1000th prime is, so you'll have to fix that, too.

Answer 8

And one more quick style point. I think you intend primelist to hold all the primes you've found, and for primeN to be the number of primes you've found. If that's the case then primeN will be the length of primelist, which you can get from len(primelist). That's one less variable you have to maintain. I think len() is fast, so there's no benefit to storing the length separately. In fact, there's only potential for harm, when it gets out of synch with primelist. In programming we call that "single source of truth." When you have two variables that have to agree, what do you do when they disagree? Avoid the issue altogether by only using one variable and deriving the value of the other variable. If you can. Here you can.

Answer 9

Yet one more final thing. Yes, you're misusing x in your commented-out code, but not really. The for loop is controlling the values x gets, so your attempt to change it will have no effect. Nonetheless, it's incorrect to change it.

So, after all that, uncomment your good code, remove the misguided attempts to change x, then remove the vestigial empty elif block with its unnecessary second test, remove the redundant primeN variable, and your code will work great. Then you'll just have to figure out how to loop correctly to find 1000 primes.

Answer 10

D!!! Wow, thank you for your exhaustive explanations. They've helped me immensely. Especially the style points....and points for being concise. I've completed this Problem set, moving on. Once again, THANK YOU.

Where can I find more about style and being more concise?

You deserve another medal, but alas I'm not able to give another. I'm sure I'll have some more questions for you down the road. Thanks again.

Answer 11

The main reason I posted so much is because I didn't fully understand everything about your code before writing an answer, so I had to correct myself a few times. But I guess I did manage to squeeze in a few good bits of advice among all the backpedaling.

Do you mind posting your final version of the code?

I think there are some good books about style and such, but I think it's better to look at them once you get more experience programming. Tough it out with the other programs in this class, and when you get a program to work start making it look and work better. Understand what each line you wrote does, understand the role of each variable, and make sure each thing serves one clear purpose. When I first started programming in college I'd suffer through writing something, and it wouldn't quite work, and the code would be confusing. Then I'd start stripping away the messy code, or just start over, and eventually I'd get the right code, and the right code tended to be pretty and clean and straightforward and short.

Use this forum. There are people here who want to help. Ask them to review your code. Once you've thought through a problem, and worked through getting the code to work, you'll have a better foundation on which to receive suggestions on style and structure.