A community for students.
Here's the question you clicked on:
 0 viewing
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/
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/

This Question is Closed

agdgdgdgwngo
 4 years ago
Best ResponseYou've already chosen the best response.0Don'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.

agdgdgdgwngo
 4 years ago
Best ResponseYou've already chosen the best response.0Even 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

agdgdgdgwngo
 4 years ago
Best ResponseYou've already chosen the best response.0Even MORE optimized http://ideone.com/0duq9 same answer, but done in 0.14 seconds instead of 0.5, and instead of 2.5 seconds in your answer.

agdgdgdgwngo
 4 years ago
Best ResponseYou've already chosen the best response.0Anyone here know how to calculate the 1000th prime number in under 100 milliseconds in Python? Besides 'print 7919' :P

agdgdgdgwngo
 4 years ago
Best ResponseYou've already chosen the best response.0for reference, here is the fastest way to display the 1000th prime number: http://ideone.com/YJ5ie

agdgdgdgwngo
 4 years ago
Best ResponseYou've already chosen the best response.0for reference, here is your code. http://ideone.com/89jy4

JonathanFichter
 4 years ago
Best ResponseYou've already chosen the best response.0I 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.

Nessman
 4 years ago
Best ResponseYou've already chosen the best response.0ok 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.

agdgdgdgwngo
 4 years ago
Best ResponseYou've already chosen the best response.010  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

agdgdgdgwngo
 4 years ago
Best ResponseYou've already chosen the best response.0woot 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

agdgdgdgwngo
 4 years ago
Best ResponseYou've already chosen the best response.0almost 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)

agdgdgdgwngo
 4 years ago
Best ResponseYou've already chosen the best response.0sure, 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

jaskaran
 4 years ago
Best ResponseYou've already chosen the best response.1wow seems like someone is really interested in making the code runs more faster .

agdgdgdgwngo
 4 years ago
Best ResponseYou've already chosen the best response.0it's good to learn how to make code run faster.

agdgdgdgwngo
 4 years ago
Best ResponseYou've already chosen the best response.0my 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

mkutz1325
 4 years ago
Best ResponseYou've already chosen the best response.0wow, 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

agdgdgdgwngo
 4 years ago
Best ResponseYou've already chosen the best response.0I'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.

Nessman
 4 years ago
Best ResponseYou've already chosen the best response.0please 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

heisemberg
 4 years ago
Best ResponseYou've already chosen the best response.0Hello. 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.
Ask your own question
Sign UpFind more explanations on OpenStudy
Your question is ready. Sign up for free to start getting answers.
spraguer
(Moderator)
5
→ View Detailed Profile
is replying to Can someone tell me what button the professor is hitting...
23
 Teamwork 19 Teammate
 Problem Solving 19 Hero
 Engagement 19 Mad Hatter
 You have blocked this person.
 ✔ You're a fan Checking fan status...
Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.