Prime Number and Primality Test

Prime Number


A prime number or (a prime) is a natural number greater than 1 and which is divisible by 1 and itself only. A natural number greater than 1 that is not prime is called a composite number.

Some first prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23 etc.

Example: 23 its factors are (1 and 23), so 23 is a prime number.
                 17 its factors are (1 and 17), so 17 is a prime number.

šŸ‘‰ 2 is the only prime number which is even and it is the smallest prime number.

Primality Test

The Primality test is basically an algorithm to check whether the input is prime or not. Among other fields of mathematics, it is used for cryptography. By using this approach we used to find the number of divisors, if the number of divisors is 2 it is prime, and if not then it is a composite number.

The pseudocode for this approach is given below.
             
                        int count = 0;
                        for( int i=1; i <= n; i++){
                             if(n%i==0)
                                 count++;
                       }
                        if(count!=2)
                               cout<< n <<" is not a Prime"<<endl;
                        else
                               cout<< n <<" is a prime number"<<endl;

The time complexity for this algorithm is O(N).

Primality test in O(sqrt(n)) time complexity

Now instead of checking till n, we can optimize our algorithm by checking till sqrt(n) because the large factor of n must be a multiple of smaller factors that have been already checked.

Below is the pseudocode for this approach.

                               bool isPrime(int num)  
                              {
                                   for(int i=2; i*i<=num; i++)
                                   {
                                           if(num%i==0)
                                               return false;         // num is composite
                                   }
                                   return true;        // num is prime
                               }

The time complexity of the above algorithm is O(sqrt(num)).

Written with šŸ’— by Manish.

Comments