Generate nth prime number in Python Today I had an interview, where I was asked to solve this problem:


  Generate nth prime number. Given a signature below, write python logic
  to generate the nth prime number:

def nth_prime_number(n):
  # n = 1 =&gt; return 2
  # n = 4 =&gt; return 7
  # n = 10 =&gt; return 29



I wrote this code, but couldn't get through:

def nth_prime_number(n):
    if n==1:
        return 2
    count = 1
    num = 3
    while(count &lt;= n):
        if is_prime(num):
            count +=1
            if count == n:
               return num
        num +=2 #optimization

def is_prime(num):
    factor = 2
    while (factor &lt; num):
        if num%factor == 0:
             return False
        factor +=1
    return True 


The overall feedback was that the code quality could be improved a lot, and that I should be more optimal in my approach. How can I improve this code?
Your is_prime() function checks if num is a multiple of any number below it. This means that it checks if it is a multiple of 2, 4, 6, 8, 10, etc. We know that if it isn't a multiple of 2, it won't be a multiple of 4, etc. This goes for all other numbers, if it isn't a multiple of 3, it won't be a multiple of 27 (3x3x3).

What you need to do is check if num is a multiple of any prime number before it.

def nth_prime_number(n):
    # initial prime number list
    prime_list = [2]
    # first number to test if prime
    num = 3
    # keep generating primes until we get to the nth one
    while len(prime_list) &lt; n:

        # check if num is divisible by any prime before it
        for p in prime_list:
            # if there is no remainder dividing the number
            # then the number is not a prime
            if num % p == 0:
                # break to stop testing more numbers, we know it's not a prime
                break

        # if it is a prime, then add it to the list
        # after a for loop, else runs if the "break" command has not been given
        else:
            # append to prime list
            prime_list.append(num)

        # same optimization you had, don't check even numbers
        num += 2

    # return the last prime number generated
    return prime_list[-1]


I'm sure someone else here will come up with an even more efficient solution, but this'll get you started.