{"id":708,"date":"2020-06-11T10:10:22","date_gmt":"2020-06-11T10:10:22","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=708"},"modified":"2022-05-23T11:13:24","modified_gmt":"2022-05-23T11:13:24","slug":"prime-numbers","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/prime-numbers\/","title":{"rendered":"Prime Numbers"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used:<\/h3>\n
\n

Mathematics<\/p>\n<\/blockquote>\n

Difficulty Level:<\/h3>\n
\n

Easy<\/p>\n<\/blockquote>\n

Problem Statement (Simplified):<\/h3>\n
\n

For a given number N<\/code>, print Yes<\/code> if it is prime, else print No<\/code>.
\nPrime Numbers:<\/em><\/strong> Numbers that are divisible by 1 and itself only are known as Prime numbers.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Test Case:<\/h4>\n
Input:\n2\n13\n14\n\nOutput:\nYes\nNo\n\nExplanation:\nCase-1:\n13 is divisible by 1 and 13 only. So 13 is a prime number.\n\nCase-2:\n14 is divisible by 1,2,7 and 14. So 14 is not a prime number.<\/code><\/pre>\n
Solving Approach :<\/h3>\n
Bruteforce Approach:<\/h4>\n
1) We can check if there exists any number between 1<\/code> and N<\/code> which divides N<\/code> completely. If such a factor exists, that means the given number is not prime and we print No<\/code>. If no such number is found, we print Yes<\/code> which means the number is Prime.
\n2) But this approach takes O(N)<\/code> time complexity as we iterate every element from 1 to N<\/code>. We can improve this time complexity more by using the more efficient approach.<\/p>\n
Efficient Approach:<\/h4>\n
1) We know if the number N<\/code> is not Prime, it will have total factors more than 2. If we pick any two factors greater than , let’s say a<\/code> and b<\/code>, then their product a x b<\/code> will be always more than N<\/code>.
\n2) So if we can’t find any factors less than or equal to the square root, N<\/code> must be prime.
\n3) So, We check numbers from 1 to , if a number is found which divides N<\/code> completely, then the number is not prime. Else number is Prime.<\/p>\n
Example:<\/h4>\n
    \n
  • Let’s assume, number to check is 500<\/code>, its square root value is 22.360<\/code>, so we check for all numbers from 2<\/code> to 22<\/code>. 5<\/code> divides 500<\/code> completely so, 500<\/code> is not a prime<\/code> number.
    \n
    <\/blockquote>\n<\/li>\n
  • Lets take another number i.e. 42403<\/code>, it’s square root is 205.919887335<\/code>, so we check for all numbers from 2<\/code> to 205<\/code>, we do not find any number in this range which divides 42403<\/code> completely, hence 42403<\/code> is prime<\/code> number.<\/li>\n<\/ul>\n
    Solutions:<\/h3>\n
    \t\t\t\t\t\t