Question

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

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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

Answer 6

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.