Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

mkutz1325

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/

  • 2 years ago
  • 2 years ago

  • This Question is Closed
  1. agdgdgdgwngo
    Best Response
    You've already chosen the best response.
    Medals 0

    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 years ago
  2. agdgdgdgwngo
    Best Response
    You've already chosen the best response.
    Medals 0

    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

    • 2 years ago
  3. agdgdgdgwngo
    Best Response
    You've already chosen the best response.
    Medals 0

    Even 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.

    • 2 years ago
  4. agdgdgdgwngo
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • 2 years ago
  5. agdgdgdgwngo
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • 2 years ago
  6. agdgdgdgwngo
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • 2 years ago
  7. JonathanFichter
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

    • 2 years ago
  8. Nessman
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

    • 2 years ago
  9. agdgdgdgwngo
    Best Response
    You've already chosen the best response.
    Medals 0

    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

    • 2 years ago
  10. agdgdgdgwngo
    Best Response
    You've already chosen the best response.
    Medals 0

    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

    • 2 years ago
  11. agdgdgdgwngo
    Best Response
    You've already chosen the best response.
    Medals 0

    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)

    • 2 years ago
  12. agdgdgdgwngo
    Best Response
    You've already chosen the best response.
    Medals 0

    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

    • 2 years ago
  13. jaskaran
    Best Response
    You've already chosen the best response.
    Medals 1

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

    • 2 years ago
  14. agdgdgdgwngo
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • 2 years ago
  15. agdgdgdgwngo
    Best Response
    You've already chosen the best response.
    Medals 0

    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

    • 2 years ago
  16. mkutz1325
    Best Response
    You've already chosen the best response.
    Medals 0

    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

    • 2 years ago
  17. agdgdgdgwngo
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

    • 2 years ago
  18. Nessman
    Best Response
    You've already chosen the best response.
    Medals 0

    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

    • 2 years ago
  19. heisemberg
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

    • 2 years ago
    • Attachments:

See more questions >>>

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
  • 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.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.