Check if a number is Prime

In programming, one very common problem asked is to check whether a given number is a prime number or composite. So, in this article, we will learn how to identify whether a number is prime or not.

A prime number is a number that can be divisible by only 2 numbers that are by 1 and by itself. This means that there are only 2 divisors for them. So numbers like 2,7,11 are examples of prime numbers.

Problem Statement:

Given an integer N, write a program to identify whether N is a prime number or a composite number.

The C++ Code to solve this problem is as follows:

Explanation:

·        We are checking whether the Number is prime or not. So we will iterate starting from 2 till less than or equal to the square root of that number.

·        This is because the numbers after the square root of that number are already divisible by the numbers before the square root.

·        So we just have to consider the numbers that come before or equal to the square root and check if our original Number is divisible by any of these numbers.

·        If it is then return false as the Number is not prime else if our Number is not divisible by any number until its square root then it means that the Number is a prime number.

Time Complexity: O(√n)

Space Complexity: O(1)