All about Prime numbers, from Introduction to Application including Generation

This is my first tutorial for this session. If you don’t know anything about prime number then don’t worry. Just read and practice carefully the tutorial below. I think after completing my tutorial you probably will be an expert in prime term.

If you know many thing about prime then just look down and don’t miss the complexity section.

I am dividing this tutorial in several sections as follows:

• Prime Introduction
• Prime Generation simple and less efficient and must know technique
• Practice section
• About next tutorial

Prime Introduction  

 
Q. What is Prime number?
Answer: A number (must be natural and positive) which is greater than 1 and has no divisor other than 1 and itself is called a prime number.
For example,  

• 2 is a prime number. Because it is greater than 1 and has no divisor other than 1 and 2 itself.
• 3 is a prime number. Because it is greater than 1 and has no divisor other than 1 and 3 itself.
• 6 is not a prime number. Because it is also divisible by 2 and 3 other than 1 and 6 itself. So, its not a prime number.

I think you are now clear about the basic prime number definition.

Prime Generation simple and less efficient and must know technique 

 
There are many ways to generate prime numbers. I shall describe two of this. One is here. And other is in another section in below.

Suppose, n is a number to test prime or not!!

As our definition say, A Prime number is divisible by only 1 and itself. So, we don’t need to check it by 1 and n. rather we shall check it by 2 to (n-1). If the number to test (n) is divisible by any of this number from 2 to (n-1) then it breaks the rule to be prime number and hence it is not a prime. But if it is not divisible by any number between 2 to (n-1) then it satisfy the rule to be prime number and hence it is a prime number.

For example,
Suppose n=5.
Then we shall check it by 2 to (n-1): 2,3,4.
For 2, n%2! =0, not divisible.
For 3, n%3! =0, not divisible.
For 4, n%4! =0, not divisible.
Here, n=5 is not divisible by any number from 2 to (n-1)=4. So, n=5 is a prime number.

Suppose n=6.
Then we shall check it by 2 to (n-1): 2,3,4,5.
For 2, n%2 ==0, divisible.
For 3, n%3 ==0, divisible.
For 4, n%4! =0, not divisible.
For 5, n%5! =0, not divisible.
Here, n=6 is divisible by 2 and 3 and it has divisors 2 and 3 rather than 1 and 6. So, n=6 is not a prime.

How to code:
It can be implemented using a single loop as like follows:

Suppose, We shall check for n !!!

int i,n;
for(i=2;i<=(n-1);i++)
{
 if(n%i==0)
 {

  printf(“It is divisible by a number rather than 1 and itself. So n is not a prime.”);

  break;
 }
}
if(i==n) printf(“It is not divisible by any number rather than 1 and itself. So n is a prime.”);

Several question and answer about the above code:

1. Q1. Here you may ask me a question that why I have used break statement when 'if (n%i==0)' condition is satisfied???
2. Q2. Why have you used the condition ’if(i==n)‘???

Answer Q1: (n%i==0) condition will only be satisfied if n is divisible by i. As we know, n will not be prime if it is divisible by any number without 1 and n, since n is divisible by I(any number) so n is not a prime number and I have got my answer.  So I don’t need to check n by others. So, I have broken the loop.

Answer Q2:  See, if n is divisible by any I, then it will satisfy the condition (n%i==0) and will execute the break statement that will break the for loop. But if n is not divisible by any I, then it not satisfy the condition (n%i==0) and will not break the loop. So, loop will be continuing until I reached to a value greater than (n-1). In this case, I will reach to the immediate value of (n-1) which is n.
So, if I can reach to n, then n is a prime number since no value from 2 to (n-1) can divide n. 

Practice section

I think you have learn the easiest procedure to generate prime very smartly. Now, Some task for you to practice:

1. Q1. Generate all primes from 1 to 100.
2. Q2. Check if 100 is a prime or not?
3. Q3. Generate all primes from 1 to 1000000.  

Answer Q1: 
The question is to generate all primes from 1 to 100. We can do this easily. I hope, reading the above part sincerely you can now easily generate a single prime number. Ok, this is enough for further processing :) . 
To generate prime from 1 to 100, you just need a for loop which will be run for 1 to 100. Now, Suppose 'i' is the variable which will count loop(loop counter) and also contain the number from 1 to 100. Now,  for every 'i' we just check that is this number is prime or not!!! If this is prime than we'll print it otherwise skip it. 
By definition 1 is not prime so we shall start from 2.
The pseudo-code can be as follow:

1. define i,j;
2. for i=2 to 100
     for j=2 to (i-1)
        if(i%j==0) then print: i is not prime
                     break;
        else continue the inner loop.
     if(i==j) then print: i is a prime number
     end for
3. end for

Answer Q2: 
This is also is a very common and easy. You just test for 100 and if it is prime then output that is is prime otherwise output this is not prime.
In the above pseudo-code you just need to cut the outer loop ant set the value of i equal to 100.
Please try yourself to code.

Answer Q3: 
This is same as the first question and answer is same if you replace 100 by 1000000. But why I make it separate question !!! This is one of the case where this method of prime generation is going to be slow and inefficient.
Since, people want something efficient so there's a new method of prime generation called famous Sieve of Eratosthenes method which I'll explain in the next tutorial of this session.

Practice Problem :

1. UVA 543 - Goldbach's Conjecture (Level One)

About next tutorial

Today I am very tired after writing this long tutorial. I shall explain this fantastic method in the next tutorial of this session. So, please stay in touch and comment if there's any bug in this tutorial.


Next Tutorial Link: Prime Generation: Sieve of Eratosthenes Method and its Complexity analysis


 H A P P Y   C O D I N G ! !! !!!