# 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:

17

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)

Implementation of this method :

#include <bits/stdc++.h> using namespace std; int main() { int n,i,f=1; cin>>n; // n: given number // f: flag // sqrt(n) finds the squreroot of n for(i=2;i<=sqrt(n);i++) { if(n%i==0) { f=0; break; } } if(n==1) cout<<"none"; else if(f==1) cout<<"prime"; else cout<<"composite"; return 0; }

Input:

19

Output:

prime

Also, learn:

## Leave a Reply