Python - Get nth prime number

 Let us try to solve the 7th problem in Euler's project which is to get the 10,001st prime number. We will start with writing a function to check if a number is prime or not.

from math import sqrt

def isPrime(x):
    if x < 2:
        return False
    if x == 2 or x == 3:
        return True
    for i in range(2, int(sqrt(x)) + 1):
        if x % i == 0:
            return False

    return True

Let us try this in Repl:

>>> isPrime(6)
False
>>> isPrime(13)
True
>>> 

  Now we will write a function to get the nth prime, i.e,  if n is 3, we should get 5 which is the 3rd prime number.

def getNthPrime(x):
    cnt = 0
    num = 2
    while True:
        if isPrime(num):
            cnt = cnt + 1
            if cnt == x:
                return num
        num = num + 1

Testing in REPL:

>>> getNthPrime(3)
5
>>> getNthPrime(5)
11

  Similarly to get the 10,001st prime number:

>>> getNthPrime(10001)
104743
>>>

 Lets find out the time elapsed to get this:

>>> from timeit import timeit
>>> 
>>> timeit('getNthPrime(10001)', globals=globals(), number = 1)
0.289607039999737
>>> 

   All it took is just a quarter of a second to get the 10,001st prime.

Using itertools:
    getNthPrime function can be completely avoided by using itertools. itertools has 2 important functions:
  islice - returns an iterator of a slice of values
  count - returns an iterator of values. Similar to range function, but it does not take the end value.
>>> islice((x for x in count() if isPrime(x)),10001)

<itertools.islice object at 0x7fbc350ab8b8>
>>> 
>>> list(islice((x for x in count() if isPrime(x)),10001))[-1]
104743
>>> 

 Using the count we get an iteration of infinite list of numbers and only the prime ones are filtered. islice takes the 1st 10,001 numbers and stops the iteration.
   The result is taken in list context and we print the last element which is the 10,0001st prime.

>>> timeit('list(islice((x for x in count() if isPrime(x)),10001))[-1]', globals = globals(), number = 1)
0.3422034679997523
>>> 

  Time taken is almost same as what it took in the earlier one.

Tweet