Question

PS1 Please refractor this code: http://chopapp.com/#f8dcsi0v
After about 3 hours I finally figured this out - the code works, but I am sure there is a better way to do it. Thanks for the help!

Answer 1

I tried to tweak your code as is but couldn't quite get it to do what I wanted. It is probably slow because in line 11, you are finding the remainder of x divided by every "i" between 2 and x. All you have to test up to is the square root of x + 1. I tried to implement this in your code but got an error.

Here is the function I wrote to test if a number is prime.
http://codepad.org/G5lkALwF

Hopefully this is helpful, I am pretty new to this myself (just finished ps4).

Answer 2

@andreipop Instead of checking for divisibility by every number from 2 to "i" it is sufficient to only check for divisibility by prime numbers between 2 and "i". This is based on the Fundamental Theorem of Arithmetic which says every whole number can be factored into prime numbers. Here is my implementation http://chopapp.com/#j7murz5k . I hope this helps.

Answer 3

First some style issues. Don't name boolean variables in the negative (notPrime). It's harder for readers (including the author) to understand (and easier to make mistakes when using the variable later). Name them in the positive (isPrime) and if you want to test for the negative in a condition, use the "not" keyword (if not isPrime). Also, don't compare boolean variables to True or False. Just use the variable.

Here's your line 21:
if notPrime == False:
Here's what it would look like using these suggestions:
if isPrime:
Reading the code is almost like reading English.

Other than that, some minor issues:
1. Initialize the primes list to [2], just because it's slightly more correct.
2. Name the counter variable something a little clearer, like numPrimesFound. (To be really pedantic, you don't even need a variable for this, you can just call len(primes).)
3. You don't need to pop the list to get the last prime, you can just access it: last = primes[-1]. Popping it actually removes it from the list.

Answer 4

So, you asked for a better way to do it, which I took to mean a better algorithm. But I think your overall algorithm is correct. seanlerner and suaravrt both mentioned that you could reduce the loop limit to increase performance, but that's just tweaking the performance without really changing the overall algorithm. So, I thought I'd go down that route and see how much you could really improve the performance by squeezing out the most likely inefficiencies.

I wrote a test harness ( http://codepad.org/fP6dkoKr) that would compare your original implementation with my refactored version. That way I'd know I didn't break anything, and it would give me a nice quantitative measure of how much things had sped up. Then I saw what effect each change had.

1. You increment x by 1 at the end of each trip through the while loop, and if it's even you increment it again. So I just incremented it by 2 and took out the parity check and the else branch. This had 0% impact on performance.

2. On line 13 you initialize notPrime to False. This happens every time through that loop, until you hit that if condition (sets it to True and breaks) or the loop ends (and it's left False). You can move that initialization outside of the for loop. I didn't think this would make much of a difference, but it meant a 31% speed improvement over your code. That was significant, and surprising.

3. Changing the loop limit to x/2+1 made the code about 130% faster than the original.

4. Changing the loop limit to ceil(sqrt(x)) made it about 4200% faster than the original.

5. Using the already-found primes list to only test prime divisors up to and including ceil(sqrt(x)) made it 10000% (ten thousand percent) faster than the original. (This actually ran into a problem when the primes list wasn't initialized to [2], so I had to make that change, too.)

I don't really know what 10000% faster means. I probably should have just given the average times. The original code took about 960ms to find the 1000th prime. The fastest version took 10ms. I was very surprised by how dramatic the difference was.

But, having said all this, COMPLETELY IGNORE IT! First and foremost, get your code to work properly. Go ahead and test all divisors up to the number. Once you know you can find primes reliably, then you can try to find them efficiently. And before you go optimizing your code, save a backup of the working version. Or create a test that will tell you when you've broken something, and then run the test constantly, even after seemingly minor changes that you know didn't break anything, because they did.

Answer 5

Great answers - thank you for your help guys! I think my lack of mathematical background is also a factor here. Going to keep plugging away, posting my stuff to get feedback, and trying to give back when I can. Great community :)

PS @dmancine your latest codepad posting didn't show up (404) - would love to see it.

Answer 6

GAAAH!! Why does codepad keep nuking my posts?!?!

Fine. I'm posting to 4 different sites. The one that wants me to use it will keep my code around.
http://dpaste.com/hold/631718/
http://pastebin.com/Vi888gY9
http://ideone.com/kiOPa
http://codepad.org/ci5rpEAp

And just for good measure, I'll attach the file.

I won't paste the code into this post. Unless it comes to that. >:|