Prime Numbers

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.
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 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")

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.