Showing posts with label nth. Show all posts
Showing posts with label nth. Show all posts

Thursday, October 2, 2014

Finding nth prime number (large number) (Optimization)

This was something handy I learned. Actually the problem is pretty easy, but when finding the nth prime where n>1000000 it takes way to long in the conventional way youre thinking. Here is an optimized solution to it, that reduces the time complexity. If you have any doubts, ask!

I think you can even optimize it further by doing p=p+2 and num=num+2. Try it out and see

def prime(chk):
if(chk%2==0):
return False
else:
p=3
while(p<chk**0.5+1):
if(chk%p==0):
return False
p=p+1
return True



def is_prime(x):
count=2
num=4
while(count<x):
if prime(num):
count+=1
num1=num
num=num+1
return num1

result=is_prime("Enter the nth term here")
print result