A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

anonymous

  • 5 years ago

So, I finally got PS1 working correctly. But, I was wondering how I might be able to improve it to make the code more efficient. Aside from PS0, this was my first real program, and I want to learn how to make it as efficient as possible. prime_count = 1 current_number = 3 current_prime = 2 divisor = 2 desired_prime_count = raw_input('Which nth prime do you want to find?') desired_prime_count = int(desired_prime_count) while prime_count < desired_prime_count: if current_number % 2 == 0: current_number += 1 else: if current_number % divisor > 0: divisor += 1 elif current_number % div

  • This Question is Closed
  1. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    elif current_number % divisor == 0 and divisor < current_number: current_number += 1 divisor = 2 else: current_prime = current_number prime_count += 1 divisor = 2 current_number += 1 prime_count = str(prime_count) print 'The '+prime_count+'th prime number is',current_prime

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

    sorry, it cut the code off halfway through. Anyway, since the "current_number" starts at 3, I could increment by 2, eliminating the need for the first if...else statement. But what other ways might I be able to improve the code? I saw that others used the "for" loop, but I didn't want to use anything that wasn't covered in the first 2 lectures or the first 3 chapters of the book, so I stuck with the "while" loop and "if" conditional.

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

    You'll need a while loop at a minimum on the outermost iteration. The inner one can be a for or a while since you know exactly how many times you want to loop at most.

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

    If you are concerned about efficiency, perhaps the biggest improvement you could make would be recognizing primes earlier. Currently to recognize that 7919 is prime, you divide by all odd numbers up to 7919. But when we know that 7919 has no divisors up to 87, we can stop, because at the next test 89*89 is already > 7919.

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

    prime_count = 1 current_number = 3 current_prime = 2 divisor = 2 desired_prime_count = raw_input('Which nth prime do you want to find?') desired_prime_count = int(desired_prime_count) while prime_count < desired_prime_count: if current_number % divisor > 0: if divisor * divisor < current_number: divisor += 1 else: divisor = 2 prime_count += 1 current_prime = current_number current_number += 2 elif current_number % divisor == 0 and divisor < current_number: current_number += 2 divisor = 2 else: current_prime = current_number prime_count += 1 divisor = 2 current_number += 2 prime_count = str(prime_count) print 'The '+prime_count+'th prime number is',current_prime

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

    So, those are the changes I made to the code. Slight changes, I know. But WOW did it make a HUGE difference. Thank you so much. With the old code, I would have to wait more than 5 minutes (on my computer) to get the 10,000th prime. With these minor changes, I was literally able to get the 10,000th prime in a little under 15 seconds. Wow...just...wow. Such a huge difference. Thank you so much. zifmia, your suggestion made complete mathematical sense, and made such a huge difference. I'm still wowed by the increase in the speed of the code.

  7. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

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.