## mkutz1325 4 years ago just finished the first part of problem set 1. I'm wondering if there is any way to make this code more efficient, it doesn't seem like it's the best way to do this but it works. http://dpaste.com/hold/583276/

1. agdgdgdgwngo

Don't worry too much about code efficiency when you're just beginning. It's good to learn how to make your code work better, but it's most important to make sure the code is doing exactly what you want it to do (i.e. no bugs). Writing code that works properly is challenging enough. Instead of using range you can use xrange(1, 35000, 2) so you don't store about 17500 numbers in memory. Otherwise, your code already uses one of the most efficient algorithms out there.

2. agdgdgdgwngo

Even more optimized: http://ideone.com/6vvEv same answer, but done in 0.5 seconds instead of 2.5 if you want to print all the prime numbers up to 1000, just add a print 2, somewhere before the for loop, and a print j, after the isPrime check

3. agdgdgdgwngo

4. agdgdgdgwngo

Anyone here know how to calculate the 1000th prime number in under 100 milliseconds in Python? Besides 'print 7919' :-P

5. agdgdgdgwngo

for reference, here is the fastest way to display the 1000th prime number: http://ideone.com/YJ5ie

6. agdgdgdgwngo

for reference, here is your code. http://ideone.com/89jy4

7. JonathanFichter

I have to say I'm quite impressed with the clean and readable style both of you are using to write this code. My attempt was much messier. I really like the way you're using "range" --I should have done that. The one thing that I might be able to contribute is narrowing down the number of divisors you need to be checking in each loop. Lines 7 and 11 of your original code suggest that you're checking divisors growing to the size of half the candidate you're testing for prime. A few folks helpfully pointed out to me that you don't need to test this many: once the divisor gets to be the size of the square root of the candidate, you're all set and can stop checking.

8. Nessman

ok to answer agdgdgdgwngo, who asked if you can get the 1000th prime in less then 100 miliseconds in python: this code finishes in 0.03... seconds http://dpaste.com/583581/ also take your own advice and stop worrying about optimization, by the time you finish the course you'll learn to look up other peoples code, it will be better, it will be simpler, and it will run faster then your first draft would and it takes a very short time to convert compared to writing something from scratch. in this case google "python prime numbers" and you'll find code that looks like the above, it used to be the top result, maybe you can find faster code now. the point of this assignment isn't to do code fast, or optimal, its to learn how to think in sequence, its amazing how many people jump the gun on this one, they just try to hard. watch the video and try not to get ahead of the prof, at least for the first two or three assignments, he asks you to run wild later. a skill you'll find useful after the course is over.

9. agdgdgdgwngo

10 - 40 ms :-D super optimization I want to learn how he accomplished that. People probably use algorithms even more efficient than that to crack encrypted stuff. http://ideone.com/t5uTz

10. agdgdgdgwngo

woot I created even more optimized code than http://ideone.com/t5uTz after stealing one line of code from it. I can print 100000 prime numbers in ~20 seconds while his code does the same in ~33 seconds :-D

11. agdgdgdgwngo

almost forgot, here's my new one: http://ideone.com/JW4Ma compared to his: http://ideone.com/t5uTz also, my code takes ~405 seconds (a little less than 7 minutes) to print 1 million prime numbers his code takes much longer, ~560 seconds (mine is faster by 155 seconds) (40 seconds less than 10 minutes)

12. agdgdgdgwngo

sure, he has fewer lines than me, but my code is ultimately faster. If printing the billionth prime number takes my code a day, his code might take 3 days. Can anyone do a faster one? This is the benchmark for the fastest '1000th prime number': http://ideone.com/uzCAH in 0.0000200271606445 seconds This is my own code: http://ideone.com/JW4Ma in 0.0168302059174 seconds

wow seems like someone is really interested in making the code runs more faster .

14. agdgdgdgwngo

it's good to learn how to make code run faster.

15. agdgdgdgwngo

my replacing import time with from time import time, I've further optimized my code. now instead of taking 405 seconds to print 1 million prime numbers, it takes ~290 seconds

16. mkutz1325

wow, thanks for all the help everyone. I will take your advice and try not to focus on optimization too much yet. Definitely impressed at how fast some of these are though, nice work

17. agdgdgdgwngo

I've further optimized the code. instead of 'import time', use 'from time import time', also removing the need to reference the time object. This further increases code efficiency. I'm sure there are even more ways to make http://ideone.com/JW4Ma go even faster.

18. Nessman

please wait until you learn the properties of a list before you start messing with one, and until the prof starts talking about optimization before you try and make code run faster. you know you should append odd to primes instead of adding your line 16 should read: primes.append(odd) your method can cause problems in longer runs of code also just google "python prime numbers" I'm sure you'll find some of the fastest possible code out there, the prof spends quite a while teaching you how to search the internet for this stuff quickly

19. heisemberg

Hello. This is my code for prime numbers ps1a.py: http://ideone.com/3AbYo I don't used any function but instead the intuitive idea of a lista.