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

No comments:

Post a Comment