One of the most common programming exercise for beginners is, write a program to check if given number is prime or not? There are many methods to check if a number is prime or not, but most common of them is trial division, which is what we will see in this tutorial. In my opinion, these kind of program is their first steps towards algorithmic understanding. You first come with a solution, which is driven by the fact that

*prime numbers*are natural numbers, which are not divisible by any positive number other than 1 and themselves. You write a for loop to check every number, starting from 1 to given number, to see if given number is divisible by any positive number or not. This leads you to the solution. Then you find some more fact that there is no need to check till N-1, where N is the number we are checking for primeness, and checking till square root of N is enough. This reduces a lot of time, especially while*checking a large number is prime or not*.