0

I just started to learn how to program and I was trying to make a program to find the nth prime number. And I did it. But it takes a very long time for large number. Is there a way to make it faster? Here's the code I used(it's really basic):

def prime_finder(nth1):
   s = 1
   n = 0
   while n < nth1:
       s += 1
       for x in range(2,s):
          if s % x == 0:
             break
       else:
          n += 1

   return s

print prime_finder(31337)
White Shadow
  • 444
  • 2
  • 10
  • 26
Noob Ism
  • 1
  • 1
  • one method is to adapt a [prime sieve](https://en.wikipedia.org/wiki/Generating_primes#Prime_sieves) algorithm, possibly with some of the existing relatively-tight upper bounds on the *n*-th prime number. in terms of easier fixes, you only need to check divisibility for 2 through sqrt(s), which could speed it up a little :) – obataku Jun 24 '16 at 17:36
  • This is less about Python and more about [algorithms](https://en.wikipedia.org/wiki/Algorithm). Try looking at [the Sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes), for example. There is pseudo-code there that should get you started. Also, you can just google for "finding prime numbers" to find more. – rkersh Jun 24 '16 at 17:38

1 Answers1

1

You could speed it up by instead of iterating range(2,s) to find a factor, try range(2,int(math.sqrt(s))) If a number doesn't divide anything less than its square root, it must be prime.

Remember to import math

as well.

nullen
  • 11
  • 2