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

#include <stdio.h> int main() { int test; scanf("%d", &test); while(test--){ int n; scanf("%d", &n); int prime = 1; for(int i=2; i<=sqrt(n); i++){ if(n%i==0){ prime = 0; break; } } if(prime) printf("Yes\n"); else printf("No\n"); } return 0; }

#include <bits/stdc++.h> using namespace std; int main() { int test; cin>>test; while(test--){ int n; cin>>n; int prime = 1; for(int i=2; i<=sqrt(n); i++){ if(n%i==0){ prime = 0; break; } } if(prime) cout<<"Yes\n"; else cout<<"No\n"; } return 0; }

import java.util.*; import java.io.*; import java.lang.Math; public class Main { public static void main(String args[]) throws IOException { Scanner sc = new Scanner(System.in); int test = sc.nextInt(); while(test!=0){ int n = sc.nextInt(); int prime = 1; for(int i=2; i<=Math.sqrt(n); i++){ if(n%i==0){ prime = 0; break; } } if(prime==1) System.out.println("Yes"); else System.out.println("No\n"); test--; } } }