Prime Numbers in a given range - Tutorial [Updated]

Problem Statement: Given a and b, find prime numbers in a given range [a,b], (a and b are included here).

Examples:

Examples:
Input: 2 10
Output: 2 3 5 7 
Explanation: Prime Numbers b/w 2 and 10 are 2,3,5 and 7.

Example 2:
Input: 10 16
Output: 11 13 
Explanation: Prime Numbers b/w 10 and 16 are 11 and 13.

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Approach: Prime numbers b/w a and b can be found out by iterating through every number from a and b and checking for the number whether it is a prime number or not.

For E.g.

a=10

b=18

Let’s begin from 10

10 is not prime.
11 is prime.
12 is not prime.
13 is prime.
14 is not prime.
15 is not prime
16 is not prime.
17 is prime.
18 is not prime.

So, print 11, 13, and 17 as prime numbers.

Code:

C++ Code

#include <iostream>
#include <math.h>
using namespace std;
bool checkprime(int num)
{
  if (num == 1)
    return false;
  int i = 2;
  for (i = 2; i < sqrt(num); i++)
  {
    if (num % i == 0)
      return false;
  }
  return true;
}
void PrintPrimesbwrange(int a, int b)
{
  for (int i = a; i <= b; i++)
  {
    if (checkprime(i))
    {
      cout << i << " ";
    }
  }
}
int main()
{
  int a = 11, b = 17;
  PrintPrimesbwrange(a, b);
  return 0;
}

Output: 11 13 17

Time Complexity: O(N²) Since two nested loops are used.

Space Complexity: O(1)

Java Code

public class Main {
  public static boolean isPrime(int num) {
    if (num == 1)
      return false;
    for (int i = 2; i < Math.sqrt(num); i++) {
      if (num % i == 0)
        return false;
    }
    return true;
  }
  public static void PrintPrimesbwrange(int a, int b) {
    for (int i = a; i <= b; i++) {
      if (isPrime(i)) {
        System.out.print(i + " ");
      }
    }
  }
  public static void main(String args[]) {
    int a = 10, b = 17;
    PrintPrimesbwrange(a, b);
  }
}

Output: 11 13 17

Time Complexity: O(N²) Since two nested loops are used.

Space Complexity: O(1)

Special thanks to Gurmeet Singh for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article