#### Concepts Used:

Mathematics

#### Difficulty Level:

Easy

#### Problem Statement (Simplified):

For a given number

`N`

, print`Yes`

if it is prime, else print`No`

.

Numbers that are divisible by 1 and itself only are known as Prime numbers.Prime Numbers:

**See original problem statement here**

#### Test Case:

```
Input:
2
13
14
Output:
Yes
No
Explanation:
Case-1:
13 is divisible by 1 and 13 only. So 13 is a prime number.
Case-2:
14 is divisible by 1,2,7 and 14. So 14 is not a prime number.
```

#### Solving Approach :

Bruteforce Approach:

1) We can check if there exists any number between

`1`

and`N`

which divides`N`

completely. If such a factor exists, that means the given number is not prime and we print`No`

. If no such number is found, we print`Yes`

which means the number is Prime.

2) But this approach takes`O(N)`

time complexity as we iterate every element from 1 to`N`

. We can go through the best online learning sites for programming and improve this time complexity more by using the more efficient approach.

Efficient Approach:

1) We know if the number

`N`

is not Prime, it will have total factors more than 2. If we pick any two factors greater than , let’s say`a`

and`b`

, then their product`a x b`

will be always more than`N`

.

2) So if we can’t find any factors less than or equal to the square root,`N`

must be prime.

3) So, We check numbers from 1 to , if a number is found which divides`N`

completely, then the number is not prime. Else number is Prime.

#### Example:

Let’s assume, number to check is

`500`

, its square root value is`22.360`

, so we check for all numbers from`2`

to`22`

.`5`

divides`500`

completely so,`500`

is not a`prime`

number.Lets take another number i.e.

`42403`

, it’s square root is`205.919887335`

, so we check for all numbers from`2`

to`205`

, we do not find any number in this range which divides`42403`

completely, hence`42403`

is`prime`

number.

#### Solutions:

[TABS_R id=714]

[forminator_quiz id=”721″]