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