Checking Prime number the naive and the sieve method
Prime no are one of the most mysterious no. in the Number theory . There are a lot on method of checking if a no is Prime or not, two most famous are the Probabilistic and Naive method . Naive method is simple and efficient this.
Before know the better let's discuss what not to do, here is the python code for checking Prime that is less efficient.
def is_prime(num):
c=0
for i in range(2,num):
if num % i==0:
c+=1
if c==0:
return True
else:
return False
Before know the better let's discuss what not to do, here is the python code for checking Prime that is less efficient.
def is_prime(num):
c=0
for i in range(2,num):
if num % i==0:
c+=1
if c==0:
return True
else:
return False
here the loop iterates till the given number, which is useless.This can be optimized by running the first loop untill the square root of the number abd checking for the factors. This works because any composite number can be factorized and written into product of number in which one number is less than the square root of the number.HERE is the better optimized NAIVE Method for checking primes def NaivePrime(n):
check=True
for i in range(2,int(n**0.5)+1):
if i%2==0 and i !=2:
continue
else:
if n%i==0:
check=False
print "%d is factor" % i
break
return check
this runs much fast and in the conventional way if very large numbers are tested then an overflow can be encountered .
And then comes the Sieve of Eratosthenes which is much faster than previous methods given.Its modification the Sieve of Atkins is even more efficient. If space complexity is also to be taken into account then a segmented Sieve is the best method.
This is the code for Sieve of Eratosthenes
def p(n):
is_p=[False]*2 + [True]*(n-1)
for i in range(2, int(n**0.5)):
if is_p[i]:
for j in range(i*i, n, i):
is_p[j] = False
for i in range(2, n):
if is_p[i]:
yield i
print list(p(102))
0 comments