Check if a given number is Prime or Composite in C++

In this C++ tutorial, we are going to discuss some methods to check that given number is prime or composite. Firstly we will learn what is a prime number?

What is Prime number

A prime number is a number greater than 1 and which has only two factors 1 and n(itself).for example 2,3,5,7 are prime numbers.

Note:- 1 is only a number which neither a prime nor a composite.

Problem Description

There is an integer n and you have to find this is prime or not prime (composite).

Solutions

There are several methods for solving this problem with different time complexities. Here we are going to learn some of them.

Method:-1

This is a basic method to solve check if a given number is Prime or Composite in C++. In this, we use a loop from 1 to n and count all the factors if factors are equal to 2 then the given number is prime otherwise the given number is composite.

Time Complexity: O(n)

Implementation of this method :

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n,i,c=0;
  cin>>n;
// n: given number
// f: flag 
  for(i=1;i<=n;i++)
  {
      if(n%i==0)
      c++;
  }
  if(n==1)
  cout<<"none";
  else if(c==2)
  cout<<"prime";
  else
  cout<<"composite";
  return 0;
}

Input:

Output:

prime

Method-:2

In this method, we will traverse a loop from 2 to √n ( sqrt(n) ) because of the larger factor than √n are multiple of smaller factor. By using this idea we can decrease complexity from O(n) to O(√n).

Time Complexity: O(√n)