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;
}
{
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
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)
{
// Test
}
}``````

#### 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;
}
{
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()
{
// Test
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)
{
// Test
}
}``````

#### 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
}
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
}``````

#### 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;
}
{
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()
{
// Test
}
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;
}
{
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()
{
// Test
}
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

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() :
#  Test

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

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()
#  Test
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
}
}``````

#### 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()
{
// Test
}
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
{
// Test
}``````

#### 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.

Categories
Relative Post