Question

I am working on ps1a and there is something wrong with my code, but I can't figure it out.

http://codepad.org/LkkMoZSu

There is something wrong with my isPrime function, but I don't see what. Can anyone take a look and point me in the right direction?

Answer 1

I didn't actually try running your code but I'm guessing your problem is in line 10. Your comment says you're starting the range with 3 because you already accounted for 0-2, but that doesn't make any sense, as i is being used to check for primality, it's not the actual number you're checking (that's n). If I had to guess, if you change that 3 to 2, it should work fine.

Oh, and for the end of the range, you need to do int(n**0.5) + 1, because range will always stop at the number before the end value you put. So if you wanted to search every number from x to y, you would do range(x, y+1).

Also, for the thousandth() function, it might be easier on resources if you just assign whatever the last prime found was to primes, instead of keeping a list. Your function has no need to know what all of the primes are, just what the last one you find is. So you could just change line 23 to primes = iter, and then on line 28 just return primes.

Answer 2

Totally fixed it. Thanks!

Answer 3

At the top of the for loop you could have put a debug print statement like "print n, i" to make sure you were testing the correct range of divisors, then just run your isPrime() function on small numbers you know are prime/composite.

I don't think line 8 is doing what you think it's doing. Put a print statement in the body of that conditional and see if it ever gets hit. I think you want to use the mod (%) operator.

Lines 25 and 26 don't actually do anything. They can be removed.

Oh, I figured out what you were doing. You thought the "if not n and 1" was catching even numbers, so you weren't trying 2 as a divisor. I'd include 2 as a possible divisor (as kgiax already suggested), then lines 6 and 7 become unnecessary, too. Do you see why?

Other than the few little issues, your code looks very nice. As a fun extension to this problem (and since you're already storing the primes) can you change your program to use the list of primes you're accumulating to make isPrime() more efficient?

Answer 4

I see how lines 6 and 7 are unnecessary once 2 is added as a divisor (and how 25 + 26 are useless, not sure what I was thinking on putting that else: pass in there).

As for increasing the efficiency of isPrime by using stored primes previously found, I would think I could append any found prime to a list primes, and then for the next n check if n is divisible by any integer in the list primes (if it is return False), but I'm not sure how to implement that...

Answer 5

Pretty much how you're doing it. Keep the list of accumulated primes in your thousandth() method (update it each time you find a prime). But pass it in to isPrime() so it can use it.