Posted on by Kalkicode
Code Dynamic Programming

Find prime numbers between two numbers

Prime numbers are an essential concept in number theory and have practical applications in various fields, such as cryptography and computer science. In this article, we will discuss a C program that finds prime numbers between two given numbers. We will explain the problem statement, provide the algorithm used in the program, and analyze its time complexity. Let's dive in!

Problem Statement

The goal of the program is to find all prime numbers within a given range of two numbers. The program takes two integers, x and y, as input and outputs the prime numbers between x and y (inclusive).

Algorithm

The program follows the following algorithm to find prime numbers between x and y:

  1. Define a function named isPrime that takes an integer n as input and returns 1 if n is a prime number, and 0 otherwise.
  2. In the isPrime function:
    • If n is less than or equal to 1, return 0 (not prime).
    • If n is 2, 3, or 5, return 1 (prime).
    • Iterate from n/2 to 2 and check if n is divisible by any number in the range. If it is, return 0 (not prime).
    • Otherwise, return 1 (prime).
  3. Define a function named primeNumbers that takes two integers x and y as input.
  4. If x is negative or greater than y, return from the function.
  5. Calculate the size of the range by subtracting x from y and adding 1. Create an array named prime with a size of size + 1.
  6. Initialize all elements of the prime array to 1, indicating that all numbers in the range are potential prime numbers.
  7. Print the given range as (x-y).
  8. Iterate from start (initialized as x) to y.
  9. If the element at index start - x in the prime array is 1 and start is 2 or an odd number (not divisible by 2), and isPrime(start) returns 1, then:
    • Print the prime number, increment the count variable, and set the multiples of start as non-prime numbers in the prime array.
  10. Otherwise, set the element at index start - x in the prime array to 0 (not prime).
  11. Increment start by 1 and repeat steps 8-10 until start exceeds y.
  12. If no prime numbers were found (count is 0), print "None" to indicate their absence.

Code Implementation and Output

// C Program
// Find prime numbers between two numbers
#include <stdio.h>

int isPrime(int n)
{
	if (n <= 1)
	{
		return 0;
	}
	// Base case
	if (n == 2 || n == 3 || n == 5)
	{
		return 1;
	}
	// Check divisibility of a number
	for (int i = n / 2; i > 1; --i)
	{
		if (n % i == 0)
		{
			return 0;
		}
	}
	return 1;
}
void primeNumbers(int x, int y)
{
	if (x < 0 || x > y)
	{
		return;
	}
	int size = (y - x) + 1;
	int start = x;
	int count = 0;
	int prime[size + 1];
	// Initial set the all prime elements in given range
	for (int i = 0; i <= size; ++i)
	{
		prime[i] = 1;
	}
	printf("\n Given range (%d-%d)", x, y);
	printf("\n Prime number : ");
	while (start <= y)
	{
		if (prime[start - x] == 1 && (start == 2 || (start % 2 == 1)) && isPrime(start) == 1)
		{
			printf("  %d", start);
			count++;
			int i = start + start;
			// Value of start is an prime so its multiplier is can not be prime.
			// Unset its multiple.
			while (i <= y)
			{
				prime[i - start - x] = 0;
				i += x;
			}
		}
		else
		{
			prime[start - x] = 0;
		}
		start += 1;
	}
	if (count == 0)
	{
		// When prime not exist in given range
		printf(" None \n");
	}
}
int main()
{
	// Test
	primeNumbers(40, 110);
	primeNumbers(5, 29);
	return 0;
}

Output

 Given range (40-110)
 Prime number :   41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109
 Given range (5-29)
 Prime number :   5  7  11  13  19  23  29
/*
    Java Program for
    Find prime numbers between two numbers
*/
public class Prime
{
	public boolean isPrime(int n)
	{
		if (n <= 1)
		{
			return false;
		}
		// Base case
		if (n == 2 || n == 3 || n == 5)
		{
			return true;
		}
		// Check divisibility of a number
		for (int i = n / 2; i > 1; --i)
		{
			if (n % i == 0)
			{
				return false;
			}
		}
		return true;
	}
	public void primeNumbers(int x, int y)
	{
		if (x < 0 || x > y)
		{
			return;
		}
		int size = (y - x) + 1;
		int start = x;
		int count = 0;
		boolean[] prime = new boolean[size + 1];
		// Initial set the all prime elements in given range
		for (int i = 0; i <= size; ++i)
		{
			prime[i] = true;
		}
		System.out.print("\n Given range (" + x + "-" + y + ")");
		System.out.print("\n Prime number : ");
		while (start <= y)
		{
			if (prime[start - x] == true && (start == 2 || (start % 2 == 1)) && 
                isPrime(start) == true)
			{
				System.out.print(" " + start);
				count++;
				int i = start + start;
				// Value of start is an prime so its 
                // multiplier is can not be prime.
				// Unset its multiple.
				while (i <= y)
				{
					prime[i - start - x] = false;
					i += x;
				}
			}
			else
			{
				prime[start - x] = false;
			}
			start += 1;
		}
		if (count == 0)
		{
			// When prime not exist in given range
			System.out.print(" None \n");
		}
	}
	public static void main(String[] args)
	{
		Prime task = new Prime();
		// Test
		task.primeNumbers(40, 110);
		task.primeNumbers(5, 29);
	}
}

Output

 Given range (40-110)
 Prime number :  41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109
 Given range (5-29)
 Prime number :  5 7 11 13 19 23 29
// Include header file
#include <iostream>
using namespace std;
/*
    C++ Program for
    Find prime numbers between two numbers
*/
class Prime
{
	public: bool isPrime(int n)
	{
		if (n <= 1)
		{
			return false;
		}
		// Base case
		if (n == 2 || n == 3 || n == 5)
		{
			return true;
		}
		// Check divisibility of a number
		for (int i = n / 2; i > 1; --i)
		{
			if (n % i == 0)
			{
				return false;
			}
		}
		return true;
	}
	void primeNumbers(int x, int y)
	{
		if (x < 0 || x > y)
		{
			return;
		}
		int size = (y - x) + 1;
		int start = x;
		int count = 0;
		bool *prime = new bool[size + 1];
		// Initial set the all prime elements in given range
		for (int i = 0; i <= size; ++i)
		{
			prime[i] = true;
		}
		cout << "\n Given range (" << x << "-" << y << ")";
		cout << "\n Prime number : ";
		while (start <= y)
		{
			if (prime[start - x] == true && (start == 2 || (start % 2 == 1)) &&
                this->isPrime(start) == true)
			{
				cout << " " << start;
				count++;
				int i = start + start;
				// Value of start is an prime so its 
				// multiplier is can not be prime.
				// Unset its multiple.
				while (i <= y)
				{
					prime[i - start - x] = false;
					i += x;
				}
			}
			else
			{
				prime[start - x] = false;
			}
			start += 1;
		}
		if (count == 0)
		{
			// When prime not exist in given range
			cout << " None \n";
		}
	}
};
int main()
{
	Prime *task = new Prime();
	// Test
	task->primeNumbers(40, 110);
	task->primeNumbers(5, 29);
	return 0;
}

Output

 Given range (40-110)
 Prime number :  41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109
 Given range (5-29)
 Prime number :  5 7 11 13 19 23 29
// Include namespace system
using System;
/*
    Csharp Program for
    Find prime numbers between two numbers
*/
public class Prime
{
	public Boolean isPrime(int n)
	{
		if (n <= 1)
		{
			return false;
		}
		// Base case
		if (n == 2 || n == 3 || n == 5)
		{
			return true;
		}
		// Check divisibility of a number
		for (int i = n / 2; i > 1; --i)
		{
			if (n % i == 0)
			{
				return false;
			}
		}
		return true;
	}
	public void primeNumbers(int x, int y)
	{
		if (x < 0 || x > y)
		{
			return;
		}
		int size = (y - x) + 1;
		int start = x;
		int count = 0;
		Boolean[] prime = new Boolean[size + 1];
		// Initial set the all prime elements in given range
		for (int i = 0; i <= size; ++i)
		{
			prime[i] = true;
		}
		Console.Write("\n Given range (" + x + "-" + y + ")");
		Console.Write("\n Prime number : ");
		while (start <= y)
		{
			if (prime[start - x] == true && (start == 2 || (start % 2 == 1)) 
                && this.isPrime(start) == true)
			{
				Console.Write(" " + start);
				count++;
				int i = start + start;
				// Value of start is an prime so its 
				// multiplier is can not be prime.
				// Unset its multiple.
				while (i <= y)
				{
					prime[i - start - x] = false;
					i += x;
				}
			}
			else
			{
				prime[start - x] = false;
			}
			start += 1;
		}
		if (count == 0)
		{
			// When prime not exist in given range
			Console.Write(" None \n");
		}
	}
	public static void Main(String[] args)
	{
		Prime task = new Prime();
		// Test
		task.primeNumbers(40, 110);
		task.primeNumbers(5, 29);
	}
}

Output

 Given range (40-110)
 Prime number :  41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109
 Given range (5-29)
 Prime number :  5 7 11 13 19 23 29
package main
import "fmt"
/*
    Go Program for
    Find prime numbers between two numbers
*/

func isPrime(n int) bool {
	if n <= 1 {
		return false
	}
	// Base case
	if n == 2 || n == 3 || n == 5 {
		return true
	}
	// Check divisibility of a number
	for i := n / 2 ; i > 1 ; i-- {
		if n % i == 0 {
			return false
		}
	}
	return true
}
func primeNumbers(x, y int) {
	if x < 0 || x > y {
		return
	}
	var size int = (y - x) + 1
	var start int = x
	var count int = 0
	// Initial set the all prime elements in given range
	var prime = make([] bool, size + 1)

	for i:= 0;i<=size;i++ {
		prime[i] = true
	}

	fmt.Print("\n Given range (", x, "-", y, ")")
	fmt.Print("\n Prime number : ")
	for (start <= y) {
		if prime[start - x] == true && (start == 2 || (start % 2 == 1)) && isPrime(start) == true {
			fmt.Print(" ", start)
			count++
			var i int = start + start
			// Value of start is an prime so its 
			// multiplier is can not be prime.
			// Unset its multiple.
			for (i <= y) {
				prime[i - start - x] = false
				i += x
			}
		} else {
			prime[start - x] = false
		}
		start += 1
	}
	if count == 0 {
		// When prime not exist in given range
		fmt.Print(" None \n")
	}
}
func main() {

	// Test
	primeNumbers(40, 110)
	primeNumbers(5, 29)
}

Output

 Given range (40-110)
 Prime number :  41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109
 Given range (5-29)
 Prime number :  5 7 11 13 19 23 29
<?php
/*
    Php Program for
    Find prime numbers between two numbers
*/
class Prime
{
	public	function isPrime($n)
	{
		if ($n <= 1)
		{
			return false;
		}
		// Base case
		if ($n == 2 || $n == 3 || $n == 5)
		{
			return true;
		}
		// Check divisibility of a number
		for ($i = (int)($n / 2); $i > 1; --$i)
		{
			if ($n % $i == 0)
			{
				return false;
			}
		}
		return true;
	}
	public	function primeNumbers($x, $y)
	{
		if ($x < 0 || $x > $y)
		{
			return;
		}
		$size = ($y - $x) + 1;
		$start = $x;
		$count = 0;
		// Initial set the all prime elements in given range
		$prime = array_fill(0, $size + 1, true);
		echo("\n Given range (".$x."-".$y.")");
		echo("\n Prime number : ");
		while ($start <= $y)
		{
			if ($prime[$start - $x] == true && 
                ($start == 2 || ($start % 2 == 1)) && 
                $this->isPrime($start) == true)
			{
				echo(" ".$start);
				$count++;
				$i = $start + $start;
				// Value of start is an prime so its 
				// multiplier is can not be prime.
				// Unset its multiple.
				while ($i <= $y)
				{
					$prime[$i - $start - $x] = false;
					$i += $x;
				}
			}
			else
			{
				$prime[$start - $x] = false;
			}
			$start += 1;
		}
		if ($count == 0)
		{
			// When prime not exist in given range
			echo(" None \n");
		}
	}
}

function main()
{
	$task = new Prime();
	// Test
	$task->primeNumbers(40, 110);
	$task->primeNumbers(5, 29);
}
main();

Output

 Given range (40-110)
 Prime number :  41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109
 Given range (5-29)
 Prime number :  5 7 11 13 19 23 29
/*
    Node JS Program for
    Find prime numbers between two numbers
*/
class Prime
{
	isPrime(n)
	{
		if (n <= 1)
		{
			return false;
		}
		// Base case
		if (n == 2 || n == 3 || n == 5)
		{
			return true;
		}
		// Check divisibility of a number
		for (var i = parseInt(n / 2); i > 1; --i)
		{
			if (n % i == 0)
			{
				return false;
			}
		}
		return true;
	}
	primeNumbers(x, y)
	{
		if (x < 0 || x > y)
		{
			return;
		}
		var size = (y - x) + 1;
		var start = x;
		var count = 0;
		// Initial set the all prime elements in given range
		var prime = Array(size + 1).fill(true);
		process.stdout.write("\n Given range (" + x + "-" + y + ")");
		process.stdout.write("\n Prime number : ");
		while (start <= y)
		{
			if (prime[start - x] == true && 
                (start == 2 || (start % 2 == 1)) && 
                this.isPrime(start) == true)
			{
				process.stdout.write(" " + start);
				count++;
				var i = start + start;
				// Value of start is an prime so its 
				// multiplier is can not be prime.
				// Unset its multiple.
				while (i <= y)
				{
					prime[i - start - x] = false;
					i += x;
				}
			}
			else
			{
				prime[start - x] = false;
			}
			start += 1;
		}
		if (count == 0)
		{
			// When prime not exist in given range
			process.stdout.write(" None \n");
		}
	}
}

function main()
{
	var task = new Prime();
	// Test
	task.primeNumbers(40, 110);
	task.primeNumbers(5, 29);
}
main();

Output

 Given range (40-110)
 Prime number :  41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109
 Given range (5-29)
 Prime number :  5 7 11 13 19 23 29
#    Python 3 Program for
#    Find prime numbers between two numbers
class Prime :
	def isPrime(self, n) :
		if (n <= 1) :
			return False
		
		#  Base case
		if (n == 2 or n == 3 or n == 5) :
			return True
		
		i = int(n / 2)
		#  Check divisibility of a number
		while (i > 1) :
			if (n % i == 0) :
				return False
			
			i -= 1
		
		return True
	
	def primeNumbers(self, x, y) :
		if (x < 0 or x > y) :
			return
		
		size = (y - x) + 1
		start = x
		count = 0
		#  Initial set the all prime elements in given range
		prime = [True] * (size + 1)
		print("\n Given range (", x ,"-", y ,")", end = "")
		print("\n Prime number : ", end = "")
		while (start <= y) :
			if (prime[start - x] == True and 
                (start == 2 or (start % 2 == 1)) and self.isPrime(start) == True) :
				print(" ", start, end = "")
				count += 1
				i = start + start
				#  Value of start is an prime so its 
				#  multiplier is can not be prime.
				#  Unset its multiple.
				while (i <= y) :
					prime[i - start - x] = False
					i += x
				
			else :
				prime[start - x] = False
			
			start += 1
		
		if (count == 0) :
			#  When prime not exist in given range
			print(" None ")
		
	

def main() :
	task = Prime()
	#  Test
	task.primeNumbers(40, 110)
	task.primeNumbers(5, 29)

if __name__ == "__main__": main()

Output

 Given range ( 40 - 110 )
 Prime number :   41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109
 Given range ( 5 - 29 )
 Prime number :   5  7  11  13  19  23  29
#    Ruby Program for
#    Find prime numbers between two numbers
class Prime 
	def isPrime(n) 
		if (n <= 1) 
			return false
		end

		#  Base case
		if (n == 2 || n == 3 || n == 5) 
			return true
		end

		i = n / 2
		#  Check divisibility of a number
		while (i > 1) 
			if (n % i == 0) 
				return false
			end

			i -= 1
		end

		return true
	end

	def primeNumbers(x, y) 
		if (x < 0 || x > y) 
			return
		end

		size = (y - x) + 1
		start = x
		count = 0
		#  Initial set the all prime elements in given range
		prime = Array.new(size + 1) {true}
		print("\n Given range (", x ,"-", y ,")")
		print("\n Prime number : ")
		while (start <= y) 
			if (prime[start - x] == true && 
                (start == 2 || (start % 2 == 1)) && 
                self.isPrime(start) == true) 
				print(" ", start)
				count += 1
				i = start + start
				#  Value of start is an prime so its 
				#  multiplier is can not be prime.
				#  Unset its multiple.
				while (i <= y) 
					prime[i - start - x] = false
					i += x
				end

			else
 
				prime[start - x] = false
			end

			start += 1
		end

		if (count == 0) 
			#  When prime not exist in given range
			print(" None \n")
		end

	end

end

def main() 
	task = Prime.new()
	#  Test
	task.primeNumbers(40, 110)
	task.primeNumbers(5, 29)
end

main()

Output

 Given range (40-110)
 Prime number :  41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109
 Given range (5-29)
 Prime number :  5 7 11 13 19 23 29
/*
    Scala Program for
    Find prime numbers between two numbers
*/
class Prime()
{
	def isPrime(n: Int): Boolean = {
		if (n <= 1)
		{
			return false;
		}
		// Base case
		if (n == 2 || n == 3 || n == 5)
		{
			return true;
		}
		var i: Int = n / 2;
		// Check divisibility of a number
		while (i > 1)
		{
			if (n % i == 0)
			{
				return false;
			}
			i -= 1;
		}
		return true;
	}
	def primeNumbers(x: Int, y: Int): Unit = {
		if (x < 0 || x > y)
		{
			return;
		}
		var size: Int = (y - x) + 1;
		var start: Int = x;
		var count: Int = 0;
		// Initial set the all prime elements in given range
		var prime: Array[Boolean] = Array.fill[Boolean](size + 1)(true);
		print("\n Given range (" + x + "-" + y + ")");
		print("\n Prime number : ");
		while (start <= y)
		{
			if (prime(start - x) == true && 
                (start == 2 || (start % 2 == 1)) && 
                isPrime(start) == true)
			{
				print(" " + start);
				count += 1;
				var i: Int = start + start;
				// Value of start is an prime so its 
				// multiplier is can not be prime.
				// Unset its multiple.
				while (i <= y)
				{
					prime(i - start - x) = false;
					i += x;
				}
			}
			else
			{
				prime(start - x) = false;
			}
			start += 1;
		}
		if (count == 0)
		{
			// When prime not exist in given range
			print(" None \n");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Prime = new Prime();
		// Test
		task.primeNumbers(40, 110);
		task.primeNumbers(5, 29);
	}
}

Output

 Given range (40-110)
 Prime number :  41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109
 Given range (5-29)
 Prime number :  5 7 11 13 19 23 29
/*
    Swift 4 Program for
    Find prime numbers between two numbers
*/
class Prime
{
	func isPrime(_ n: Int) -> Bool
	{
		if (n <= 1)
		{
			return false;
		}
		// Base case
		if (n == 2 || n == 3 || n == 5)
		{
			return true;
		}
		var i: Int = n / 2;
		// Check divisibility of a number
		while (i > 1)
		{
			if (n % i == 0)
			{
				return false;
			}
			i -= 1;
		}
		return true;
	}
	func primeNumbers(_ x: Int, _ y: Int)
	{
		if (x < 0 || x > y)
		{
			return;
		}
		let size: Int = (y - x) + 1;
		var start: Int = x;
		var count: Int = 0;
		// Initial set the all prime elements in given range
		var prime: [Bool] = Array(repeating: true, count: size + 1);
		print("\n Given range (", x ,"-", y ,")", terminator: "");
		print("\n Prime number : ", terminator: "");
		while (start <= y)
		{
			if (prime[start - x] == true && 
                (start == 2 || (start % 2 == 1)) && 
                self.isPrime(start) == true)
			{
				print(" ", start, terminator: "");
				count += 1;
				var i: Int = start + start;
				// Value of start is an prime so its 
				// multiplier is can not be prime.
				// Unset its multiple.
				while (i <= y)
				{
					prime[i - start - x] = false;
					i += x;
				}
			}
			else
			{
				prime[start - x] = false;
			}
			start += 1;
		}
		if (count == 0)
		{
			// When prime not exist in given range
			print(" None ");
		}
	}
}
func main()
{
	let task: Prime = Prime();
	// Test
	task.primeNumbers(40, 110);
	task.primeNumbers(5, 29);
}
main();

Output

 Given range ( 40 - 110 )
 Prime number :   41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109
 Given range ( 5 - 29 )
 Prime number :   5  7  11  13  19  23  29
/*
    Kotlin Program for
    Find prime numbers between two numbers
*/
class Prime
{
	fun isPrime(n: Int): Boolean
	{
		if (n <= 1)
		{
			return false;
		}
		// Base case
		if (n == 2 || n == 3 || n == 5)
		{
			return true;
		}
		var i: Int = n / 2;
		// Check divisibility of a number
		while (i > 1)
		{
			if (n % i == 0)
			{
				return false;
			}
			i -= 1;
		}
		return true;
	}
	fun primeNumbers(x: Int, y: Int): Unit
	{
		if (x < 0 || x > y)
		{
			return;
		}
		val size: Int = (y - x) + 1;
		var start: Int = x;
		var count: Int = 0;
		// Initial set the all prime elements in given range
		var prime: Array < Boolean > = Array(size + 1)
		{
			true
		};
		print("\n Given range (" + x + "-" + y + ")");
		print("\n Prime number : ");
		while (start <= y)
		{
			if (prime[start - x] == true && 
                (start == 2 || (start % 2 == 1)) && 
                this.isPrime(start) == true)
			{
				print(" " + start);
				count += 1;
				var i: Int = start + start;
				// Value of start is an prime so its 
				// multiplier is can not be prime.
				// Unset its multiple.
				while (i <= y)
				{
					prime[i - start - x] = false;
					i += x;
				}
			}
			else
			{
				prime[start - x] = false;
			}
			start += 1;
		}
		if (count == 0)
		{
			// When prime not exist in given range
			print(" None \n");
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Prime = Prime();
	// Test
	task.primeNumbers(40, 110);
	task.primeNumbers(5, 29);
}

Output

 Given range (40-110)
 Prime number :  41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109
 Given range (5-29)
 Prime number :  5 7 11 13 19 23 29

The program is executed with two test cases: primeNumbers(40, 110) and primeNumbers(5, 29).

The first test case, primeNumbers(40, 110), finds the prime numbers between 40 and 110. The output of this test case is:

Given range (40-110)
Prime numbers:  41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109

The prime numbers between 40 and 110 are 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, and 109.

Given range (5-29)
Prime numbers:  5 7 11 13 17 19 23 29

The prime numbers between 5 and 29 are 5, 7, 11, 13, 17, 19, 23, and 29.

Time Complexity Analysis

The time complexity of the given program can be analyzed as follows:

  1. The isPrime function checks if a number is prime by iterating from n/2 to 2. This iteration has approximately n/2 steps. Therefore, the time complexity of the isPrime function is O(n/2) or O(n).

  2. The primeNumbers function has a loop that iterates from start to y, which has a maximum of y - x + 1 steps. Inside this loop, the program checks if a number is prime using the isPrime function and performs additional operations. These operations have constant time complexity.

Hence, the dominant factor in the time complexity is the iteration from start to y, which has a time complexity of O(y - x).

In summary, the time complexity of the program is O(y - x), where x and y are the given range endpoints. The program's execution time will increase as the range between x and y grows larger.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment