Concepts Used:

Mathematics

Difficulty Level:

Easy

Problem Statement (Simplified):

For a given number N, print Yes if it is prime, else print No.
Prime Numbers: Numbers that are divisible by 1 and itself only are known as 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″]

Previous post Find Substring
Next post Hero Villian

Leave a Reply

Your email address will not be published. Required fields are marked *