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

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0elif 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

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0sorry, 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.

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0You'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.

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0If 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.

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0prime_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

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0So, 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.
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.