Prime Numbers

PRIME NUMBERS Big Deal,Huh?

Prime Number is a natural number which has exactly two distinct natural number divisors: 1 and itself.

You can most probably figure out the first 10-15 primes by yourself manually. But then,here we are talking about Programming , writing code. So, the first thought that would have come into your mind  would be that of "Brute Force" approach !

Actually , you are right in thinking that checking every number till n [ n is our number till which we have to collect all primes] and dividing it by n-1 numbers to check weather it is divisible or not and so on. Brute Force as it's called.

But frankly speaking the complexity of this code/algorithm would be quite high and you don't want to that unless you don't understand the term  Complexity.

So, here comes the Savior The sieve of eratosthenes .

This algorithm is pretty straight forward and doesn't require nuclear science brains or any other brainstorming session for it's implementation.

Pseudo-code ! 

Input: an integer n > 1
 
Let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.
 
for i = 2, 3, 4, ..., √n :
  if A[i] is true:
    for j = i2, i2+i, i2+2i, ..., n:
      A[j] := false
  

Now all i such that A[i] is true are prime. 

The above Image very well illustrates the Algorithm. :)

Still have Doubts.?
This video may help I guess.

Hope your  fear of Prime Number has been conquered a little , but Believe me you are in the right direction of winning the battle.

For more such posts please comment or mail me the topics and I am happy to help. Don't orget to subscribe!