Three different ways to calculate the prime Number in c++=>
In this blog, we will see how to calculate given number is prime or not in o(N) time.
here we will see three different methods to check whether the given number is prime or not.
Method 1=>
Run Loop from 2 to n-1
we will run a loop from 2 to n-1 and if the number is divided by any number from 2 to n-1 we will return false that number is not a prime number otherwise we will return true.
Time complexity => O(N)
Method 2=>
Run loop from 2 to n/2
we will run a loop from 2 to n/2 and if the number is divided by any number from 2 to n/2 we will return false that number is not a prime number otherwise we will return true.
Time complexity => O(N/2) => O(N).
This program will be faster than method 1
Method 3=>
Run a loop from 2 to root √n
we will run a loop from 2 to √n and if the number is divided by any number from 2 to √n we will return false that number is not a prime number otherwise we will return true.
Time complexity => O(√n )
This program will be faster than methods 1 and 2.
