Program to find whether a number is prime or not - O(n|2) and O(sqrt(n)) Approach

We hope the last video very well explained you what are the prime numbers and how you can find whether a number is prime or not in O(n) time complexity.

In this video , we have discussed two approaches that are better than the naive approach discussed in last video.



First approach is to determine whether a number is prime or not in O(n/2) time complexity.

The second approach determines whether a number is prime or not in root N time complexity.

Root N approach is based on the fact that we will definitely find a prime factor of N below (sqrt(N)).

Stay tuned for more interesting problems around prime numbers.

Learn coding from experts through PrepBytes Personalised coding courses :

competitive progarmming,prime numbers,program to find program numbers,prime number in c,coding in c,prepbytes,prepbytes prime numbers,prime numbers in c++,prime numbers in java,what is a prime number,how to find a prime number,prime nmbers sqrt(n) approach,prime numbers o(n) skills,program to find prime numbers optimised approach,