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
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