Last Updated on May 23, 2022 by Ria Pathak

### 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 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--; } } }

from math import sqrt for _ in range(int(input())): n = int(input()) prime = 1 for i in range(2, int(sqrt(n)) + 1): if(n % i == 0): prime = 0 break if(prime): print("Yes") else: print("No")

[forminator_quiz id="721"]

This article tried to discuss the concept of Mathematics i.e, Prime Numbers. Hope this blog helps you understand and solve the problem of Mathematics. To practice more problems on stack you can check out MYCODE | Competitive Programming.