You only need to loop to the square of the number, because after that you'll just repeat the same numbers again. For example if you were testing for 100, after 10 you will find 20, but you already tested it while you were testing the 5, 100/5 = 20 and 100/20 = 5, if 5 didn't divide 100 so 20 won't and vice versa, so 100/a = b tests for the divisibility by a and b, only at 10 which is sqrt(100) will a and b be rapeated again but in reversed order, (e.g you a=5, b=20 and a=20, b=5). More info here
So the code will look like that
def nth_prime_number(n):
if n==1:
return 2
count = 1
num = 3
while(count <= n):
if is_prime(num):
count +=1
num +=2 #optimization
def is_prime(num):
factor = 2
while (factor * factor <= num):
if num%factor == 0:
return False
factor +=1
return True
But overall this naive method consumes lots of time, it's O(sqrt(n) * n) where n is the total number of integers tested, I suggest you learn more about Sieve of Eratosthenes, it's an algorithm for finding all primes less than n in O(n * log(log(n))) which is alot faster than the naive one.
- 106
- 5