# Count prime numbers between two numbers

Prime numbers are integers greater than 1 that have no divisors other than 1 and themselves. Counting the prime numbers between two given numbers is a common programming problem. In this article, we will discuss a Java program that efficiently calculates the count of prime numbers between two given numbers using the Sieve of Eratosthenes algorithm.

## Problem Statement

Given two integers, A and B, the task is to count the number of prime numbers between A and B (inclusive). We want to find an efficient solution to calculate this count.

## Pseudocode Algorithm with Explanation

1. Create a class called PrimeCounting to encapsulate the logic.
2. Initialize the limit of prime numbers to 1,000,000 (you can modify this value if needed).
3. Create an array called primeCount to store the count of prime numbers up to the limit.
4. Implement a constructor in the PrimeCounting class to pre-calculate prime numbers up to the limit using the Sieve of Eratosthenes algorithm.
• Create a boolean array called prime of size limit to mark the numbers as prime or non-prime.
• Initially, set all elements of the prime array as true, assuming all numbers are prime.
• Iterate from 2 to the limit:
• If the current number is marked as prime:
• Mark all its multiples as non-prime by setting their corresponding indices in the prime array to false.
• Set primeCount[0] and primeCount[1] as 0 since 0 and 1 are not prime.
• Iterate from 2 to the limit:
• Calculate the prime count for the current index:
• If the number at the current index is prime, increment the prime count.
• Set the current prime count as the prime count for the next index.
5. Implement a method called primeBetween to calculate the count of prime numbers between two given numbers, a and b:
• Initialize the result as 0.
• If both a and b are greater than 0:
• If a or b is greater than or equal to the limit, return.
• Calculate the result as primeCount[b] - primeCount[a].
• Print the prime numbers between a and b and the resulting count.
6. In the main method:
• Create an instance of the PrimeCounting class.
• Call the primeBetween method with different input ranges to demonstrate the functionality.

## Code Solution

``````// Java program for
// Count prime numbers between two numbers
public class PrimeCounting
{
public int limit;
public int[] primeCount;
public PrimeCounting()
{
// This is prime number limit
this.limit = 1000000;
this.primeCount = new int[this.limit];
this.calculatePrime();
}
// Pre calculate prime number under limit
public void calculatePrime()
{
boolean[] prime = new boolean[this.limit];
//  Set initial all element is prime
for (int i = 2; i < this.limit; i++)
{
prime[i] = true;
}
for (int i = 2; i < this.limit; ++i)
{
if (prime[i] == true)
{
// Inactive the multiple prime value of [i]
for (int j = 2 * i; j < this.limit; j += i)
{
prime[j] = false;
}
}
}
this.primeCount[0] = 0;
this.primeCount[1] = 0;
for (int i = 2; i < this.limit; ++i)
{
this.primeCount[i] = this.primeCount[i - 1];
if (prime[i] == true)
{
// When current element is prime
this.primeCount[i] = this.primeCount[i] + 1;
}
}
}
public void primeBetween(int a, int b)
{
int result = 0;
if (a > 0 && b > 0)
{
if (a >= this.limit || b >= this.limit)
{
// When range are outside the limit
return;
}
result = this.primeCount[b] - this.primeCount[a];
}
System.out.print("\n Prime between (" + a + "," + b + ") ");
System.out.print("\n Result : " + result);
}
public static void main(String[] args)
{
/*
prime number between 25-100
[
29  31  37  41  43  47  53  59  61
67  71  73  79  83  89  97
]
Result = 26

*/
/*
prime number between 1000-1200
[
1009  1013  1019  1021  1031  1033  1039
1049  1051  1061  1063  1069  1087  1091
1093  1097  1103  1109  1117  1123  1129
1151  1153  1163  1171  1181  1187  1193
]
Result = 28
*/
}
}``````

#### Output

`````` Prime between (25,100)
Result : 16
Prime between (1000,1200)
Result : 28``````
``````// Include header file
#include <iostream>
using namespace std;

// C++ program for
// Count prime numbers between two numbers
class PrimeCounting
{
public: int limit;
int *primeCount;
PrimeCounting()
{
this->limit = 1000000;
this->primeCount = new int[this->limit];
this->calculatePrime();
}
// Pre calculate prime number under limit
void calculatePrime()
{
bool prime[this->limit];
//  Set initial all element is prime
for (int i = 2; i < this->limit; i++)
{
prime[i] = true;
}
for (int i = 2; i < this->limit; ++i)
{
if (prime[i] == true)
{
// Inactive the multiple prime value of [i]
for (int j = 2 *i; j < this->limit; j += i)
{
prime[j] = false;
}
}
}
this->primeCount[0] = 0;
this->primeCount[1] = 0;
for (int i = 2; i < this->limit; ++i)
{
this->primeCount[i] = this->primeCount[i - 1];
if (prime[i] == true)
{
// When current element is prime
this->primeCount[i] = this->primeCount[i] + 1;
}
}
}
void primeBetween(int a, int b)
{
int result = 0;
if (a > 0 && b > 0)
{
if (a >= this->limit || b >= this->limit)
{
// When range are outside the limit
return;
}
result = this->primeCount[b] - this->primeCount[a];
}
cout << "\n Prime between (" << a << "," << b << ") ";
cout << "\n Result : " << result;
}
};
int main()
{
/*
prime number between 25-100
[
29  31  37  41  43  47  53  59  61
67  71  73  79  83  89  97
]
Result = 26

*/
/*
prime number between 1000-1200
[
1009  1013  1019  1021  1031  1033  1039
1049  1051  1061  1063  1069  1087  1091
1093  1097  1103  1109  1117  1123  1129
1151  1153  1163  1171  1181  1187  1193
]
Result = 28
*/
return 0;
}``````

#### Output

`````` Prime between (25,100)
Result : 16
Prime between (1000,1200)
Result : 28``````
``````// Include namespace system
using System;
// Csharp program for
// Count prime numbers between two numbers
public class PrimeCounting
{
public int limit;
public int[] primeCount;
public PrimeCounting()
{
// This is prime number limit
this.limit = 1000000;
this.primeCount = new int[this.limit];
this.calculatePrime();
}
// Pre calculate prime number under limit
public void calculatePrime()
{
Boolean[] prime = new Boolean[this.limit];
//  Set initial all element is prime
for (int i = 2; i < this.limit; i++)
{
prime[i] = true;
}
for (int i = 2; i < this.limit; ++i)
{
if (prime[i] == true)
{
// Inactive the multiple prime value of [i]
for (int j = 2 * i; j < this.limit; j += i)
{
prime[j] = false;
}
}
}
this.primeCount[0] = 0;
this.primeCount[1] = 0;
for (int i = 2; i < this.limit; ++i)
{
this.primeCount[i] = this.primeCount[i - 1];
if (prime[i] == true)
{
// When current element is prime
this.primeCount[i] = this.primeCount[i] + 1;
}
}
}
public void primeBetween(int a, int b)
{
int result = 0;
if (a > 0 && b > 0)
{
if (a >= this.limit || b >= this.limit)
{
// When range are outside the limit
return;
}
result = this.primeCount[b] - this.primeCount[a];
}
Console.Write("\n Prime between (" + a + "," + b + ") ");
Console.Write("\n Result : " + result);
}
public static void Main(String[] args)
{
/*
prime number between 25-100
[
29  31  37  41  43  47  53  59  61
67  71  73  79  83  89  97
]
Result = 26

*/
/*
prime number between 1000-1200
[
1009  1013  1019  1021  1031  1033  1039
1049  1051  1061  1063  1069  1087  1091
1093  1097  1103  1109  1117  1123  1129
1151  1153  1163  1171  1181  1187  1193
]
Result = 28
*/
}
}``````

#### Output

`````` Prime between (25,100)
Result : 16
Prime between (1000,1200)
Result : 28``````
``````<?php
// Php program for
// Count prime numbers between two numbers
class PrimeCounting
{
public \$limit;
public \$primeCount;
public	function __construct()
{
\$this->limit = 100000;
\$this->primeCount = array_fill(0, \$this->limit, 0);
\$this->calculatePrime();
}
// Pre calculate prime number under limit
public	function calculatePrime()
{
//  Set initial all element is prime
\$prime = array_fill(0, \$this->limit, true);

for (\$i = 2; \$i < \$this->limit; ++\$i)
{
if (\$prime[\$i] == true)
{
// Inactive the multiple prime value of [i]
for (\$j = 2 * \$i; \$j < \$this->limit; \$j += \$i)
{
\$prime[\$j] = false;
}
}
}
\$this->primeCount[0] = 0;
\$this->primeCount[1] = 0;
for (\$i = 2; \$i < \$this->limit; ++\$i)
{
\$this->primeCount[\$i] = \$this->primeCount[\$i - 1];
if (\$prime[\$i] == true)
{
// When current element is prime
\$this->primeCount[\$i] = \$this->primeCount[\$i] + 1;
}
}
}
public	function primeBetween(\$a, \$b)
{
\$result = 0;
if (\$a > 0 && \$b > 0)
{
if (\$a >= \$this->limit || \$b >= \$this->limit)
{
// When range are outside the limit
return;
}
\$result = \$this->primeCount[\$b] - \$this->primeCount[\$a];
}
echo("\n Prime between (".\$a.",".\$b.") ");
echo("\n Result : ".\$result);
}
}

function main()
{
/*
prime number between 25-100
[
29  31  37  41  43  47  53  59  61
67  71  73  79  83  89  97
]
Result = 26

*/
/*
prime number between 1000-1200
[
1009  1013  1019  1021  1031  1033  1039
1049  1051  1061  1063  1069  1087  1091
1093  1097  1103  1109  1117  1123  1129
1151  1153  1163  1171  1181  1187  1193
]
Result = 28
*/
}
main();``````

#### Output

`````` Prime between (25,100)
Result : 16
Prime between (1000,1200)
Result : 28``````
``````// Node JS program for
// Count prime numbers between two numbers
class PrimeCounting
{

constructor()
{
this.limit = 1000000;
this.primeCount = Array(this.limit).fill(0);
this.calculatePrime();
}
// Pre calculate prime number under limit
calculatePrime()
{
//  Set initial all element is prime
var prime = Array(this.limit).fill(true);

for (var i = 2; i < this.limit; ++i)
{
if (prime[i] == true)
{
// Inactive the multiple prime value of [i]
for (var j = 2 * i; j < this.limit; j += i)
{
prime[j] = false;
}
}
}
this.primeCount[0] = 0;
this.primeCount[1] = 0;
for (var i = 2; i < this.limit; ++i)
{
this.primeCount[i] = this.primeCount[i - 1];
if (prime[i] == true)
{
// When current element is prime
this.primeCount[i] = this.primeCount[i] + 1;
}
}
}
primeBetween(a, b)
{
var result = 0;
if (a > 0 && b > 0)
{
if (a >= this.limit || b >= this.limit)
{
// When range are outside the limit
return;
}
result = this.primeCount[b] - this.primeCount[a];
}
process.stdout.write("\n Prime between (" + a + "," + b + ") ");
process.stdout.write("\n Result : " + result);
}
}

function main()
{
/*
prime number between 25-100
[
29  31  37  41  43  47  53  59  61
67  71  73  79  83  89  97
]
Result = 26

*/
/*
prime number between 1000-1200
[
1009  1013  1019  1021  1031  1033  1039
1049  1051  1061  1063  1069  1087  1091
1093  1097  1103  1109  1117  1123  1129
1151  1153  1163  1171  1181  1187  1193
]
Result = 28
*/
}
main();``````

#### Output

`````` Prime between (25,100)
Result : 16
Prime between (1000,1200)
Result : 28``````
``````#  Python 3 program for
#  Count prime numbers between two numbers
class PrimeCounting :
def __init__(self) :
self.limit = 1000000
self.primeCount = [0] * (self.limit)
self.calculatePrime()

#  Pre calculate prime number under limit
def calculatePrime(self) :
#   Set initial all element is prime
prime = [True] * (self.limit)
i = 2
while (i < self.limit) :
if (prime[i] == True) :
j = 2 * i
#  Inactive the multiple prime value of [i]
while (j < self.limit) :
prime[j] = False
j += i

i += 1

self.primeCount[0] = 0
self.primeCount[1] = 0
i = 2
while (i < self.limit) :
self.primeCount[i] = self.primeCount[i - 1]
if (prime[i] == True) :
#  When current element is prime
self.primeCount[i] = self.primeCount[i] + 1

i += 1

def primeBetween(self, a, b) :
result = 0
if (a > 0 and b > 0) :
if (a >= self.limit or b >= self.limit) :
#  When range are outside the limit
return

result = self.primeCount[b] - self.primeCount[a]

print("\n Prime between (", a ,",", b ,") ", end = "",sep="")
print("\n Result : ", result, end = "")

def main() :
#    prime number between 25-100
#    [
#        29  31  37  41  43  47  53  59  61
#        67  71  73  79  83  89  97
#    ]
#    Result = 26
#    prime number between 1000-1200
#    [
#        1009  1013  1019  1021  1031  1033  1039
#        1049  1051  1061  1063  1069  1087  1091
#        1093  1097  1103  1109  1117  1123  1129
#        1151  1153  1163  1171  1181  1187  1193
#    ]
#    Result = 28

if __name__ == "__main__": main()``````

#### Output

`````` Prime between (25,100)
Result :  16
Prime between (1000,1200)
Result :  28``````
``````#  Ruby program for
#  Count prime numbers between two numbers
class PrimeCounting
# Define the accessor and reader of class PrimeCounting
attr_accessor :limit, :primeCount
Array.new() {0}
def initialize()
self.limit = 1000000
self.primeCount = Array.new(self.limit) {0}
self.calculatePrime()
end

#  Pre calculate prime number under limit
def calculatePrime()
#   Set initial all element is prime
prime = Array.new(self.limit) {true}
i = 2
while (i < self.limit)
if (prime[i] == true)
j = 2 * i
#  Inactive the multiple prime value of [i]
while (j < self.limit)
prime[j] = false
j += i
end

end

i += 1
end

self.primeCount[0] = 0
self.primeCount[1] = 0
i = 2
while (i < self.limit)
self.primeCount[i] = self.primeCount[i - 1]
if (prime[i] == true)
#  When current element is prime
self.primeCount[i] = self.primeCount[i] + 1
end

i += 1
end

end

def primeBetween(a, b)
result = 0
if (a > 0 && b > 0)
if (a >= self.limit || b >= self.limit)
#  When range are outside the limit
return
end

result = self.primeCount[b] - self.primeCount[a]
end

print("\n Prime between (", a ,",", b ,") ")
print("\n Result : ", result)
end

end

def main()
#    prime number between 25-100
#    [
#        29  31  37  41  43  47  53  59  61
#        67  71  73  79  83  89  97
#    ]
#    Result = 26
#    prime number between 1000-1200
#    [
#        1009  1013  1019  1021  1031  1033  1039
#        1049  1051  1061  1063  1069  1087  1091
#        1093  1097  1103  1109  1117  1123  1129
#        1151  1153  1163  1171  1181  1187  1193
#    ]
#    Result = 28
end

main()``````

#### Output

`````` Prime between (25,100)
Result : 16
Prime between (1000,1200)
Result : 28``````
``````// Scala program for
// Count prime numbers between two numbers
class PrimeCounting(var limit: Int,
var primeCount: Array[Int])
{
def this()
{
this(1000000, Array.fill[Int](1000000)(0));
this.calculatePrime();
}
// Pre calculate prime number under limit
def calculatePrime(): Unit = {
//  Set initial all element is prime
var prime: Array[Boolean] = Array.fill[Boolean](this.limit)(true);
var i: Int = 2;
while (i < this.limit)
{
if (prime(i) == true)
{
var j: Int = 2 * i;
// Inactive the multiple prime value of [i]
while (j < this.limit)
{
prime(j) = false;
j += i;
}
}
i += 1;
}
this.primeCount(0) = 0;
this.primeCount(1) = 0;
i = 2;
while (i < this.limit)
{
this.primeCount(i) = this.primeCount(i - 1);
if (prime(i) == true)
{
// When current element is prime
this.primeCount(i) = this.primeCount(i) + 1;
}
i += 1;
}
}
def primeBetween(a: Int, b: Int): Unit = {
var result: Int = 0;
if (a > 0 && b > 0)
{
if (a >= this.limit || b >= this.limit)
{
// When range are outside the limit
return;
}
result = this.primeCount(b) - this.primeCount(a);
}
print("\n Prime between (" + a + "," + b + ") ");
print("\n Result : " + result);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: PrimeCounting = new PrimeCounting();
/*
prime number between 25-100
[
29  31  37  41  43  47  53  59  61
67  71  73  79  83  89  97
]
Result = 26

*/
/*
prime number between 1000-1200
[
1009  1013  1019  1021  1031  1033  1039
1049  1051  1061  1063  1069  1087  1091
1093  1097  1103  1109  1117  1123  1129
1151  1153  1163  1171  1181  1187  1193
]
Result = 28
*/
}
}``````

#### Output

`````` Prime between (25,100)
Result : 16
Prime between (1000,1200)
Result : 28``````
``````// Swift 4 program for
// Count prime numbers between two numbers
class PrimeCounting
{
var limit: Int;
var primeCount: [Int];
init()
{
self.limit = 1000000;
self.primeCount = Array(repeating: 0, count: self.limit);
self.calculatePrime();
}
// Pre calculate prime number under limit
func calculatePrime()
{
//  Set initial all element is prime
var prime: [Bool] = Array(repeating: true, count: self.limit);
var i: Int = 2;
while (i < self.limit)
{
if (prime[i] == true)
{
var j: Int = 2 * i;
// Inactive the multiple prime value of [i]
while (j < self.limit)
{
prime[j] = false;
j += i;
}
}
i += 1;
}
self.primeCount[0] = 0;
self.primeCount[1] = 0;
i = 2;
while (i < self.limit)
{
self.primeCount[i] = self.primeCount[i - 1];
if (prime[i] == true)
{
// When current element is prime
self.primeCount[i] = self.primeCount[i] + 1;
}
i += 1;
}
}
func primeBetween(_ a: Int, _ b: Int)
{
var result: Int = 0;
if (a > 0 && b > 0)
{
if (a >= self.limit || b >= self.limit)
{
// When range are outside the limit
return;
}
result = self.primeCount[b] - self.primeCount[a];
}
print("\n Prime between (", a ,",", b ,") ", terminator: "");
print("\n Result : ", result, terminator: "");
}
}
func main()
{
/*
prime number between 25-100
[
29  31  37  41  43  47  53  59  61
67  71  73  79  83  89  97
]
Result = 26

*/
/*
prime number between 1000-1200
[
1009  1013  1019  1021  1031  1033  1039
1049  1051  1061  1063  1069  1087  1091
1093  1097  1103  1109  1117  1123  1129
1151  1153  1163  1171  1181  1187  1193
]
Result = 28
*/
}
main();``````

#### Output

`````` Prime between ( 25 , 100 )
Result :  16
Prime between ( 1000 , 1200 )
Result :  28``````
``````// Kotlin program for
// Count prime numbers between two numbers
class PrimeCounting
{
var limit: Int;
var primeCount: Array < Int > ;
constructor()
{
this.limit = 1000000;
this.primeCount = Array(this.limit)
{
0
};
this.calculatePrime();
}
// Pre calculate prime number under limit
fun calculatePrime(): Unit
{
//  Set initial all element is prime
var prime: Array < Boolean > = Array(this.limit)
{
true
};
var i: Int = 2;
while (i < this.limit)
{
if (prime[i] == true)
{
var j: Int = 2 * i;
// Inactive the multiple prime value of [i]
while (j < this.limit)
{
prime[j] = false;
j += i;
}
}
i += 1;
}
this.primeCount[0] = 0;
this.primeCount[1] = 0;
i = 2;
while (i < this.limit)
{
this.primeCount[i] = this.primeCount[i - 1];
if (prime[i] == true)
{
// When current element is prime
this.primeCount[i] = this.primeCount[i] + 1;
}
i += 1;
}
}
fun primeBetween(a: Int, b: Int): Unit
{
var result: Int = 0;
if (a > 0 && b > 0)
{
if (a >= this.limit || b >= this.limit)
{
// When range are outside the limit
return;
}
result = this.primeCount[b] - this.primeCount[a];
}
print("\n Prime between (" + a + "," + b + ") ");
print("\n Result : " + result);
}
}
fun main(args: Array < String > ): Unit
{
/*
prime number between 25-100
[
29  31  37  41  43  47  53  59  61
67  71  73  79  83  89  97
]
Result = 26

*/
/*
prime number between 1000-1200
[
1009  1013  1019  1021  1031  1033  1039
1049  1051  1061  1063  1069  1087  1091
1093  1097  1103  1109  1117  1123  1129
1151  1153  1163  1171  1181  1187  1193
]
Result = 28
*/
}``````

#### Output

`````` Prime between (25,100)
Result : 16
Prime between (1000,1200)
Result : 28``````
``````package main
import "fmt"
// Go program for
// Count prime numbers between two numbers
type PrimeCounting struct {
limit int
primeCount []int
}
func getPrimeCounting() * PrimeCounting {
var me *PrimeCounting = &PrimeCounting {}
// This is prime number limit
me.limit = 1000000
me.primeCount = make([] int, me.limit)
me.calculatePrime()
return me
}
// Pre calculate prime number under limit
func(this PrimeCounting) calculatePrime() {
//  Set initial all element is prime
var prime = make([] bool, this.limit)
for i := 0 ; i < this.limit ; i++ {
prime[i] = true
}
for i := 2 ; i < this.limit ; i++ {
if prime[i] == true {
// Inactive the multiple prime value of [i]
for j := 2 * i ; j < this.limit ; j += i {
prime[j] = false
}
}
}
this.primeCount[0] = 0
this.primeCount[1] = 0
for i := 2 ; i < this.limit ; i++ {
this.primeCount[i] = this.primeCount[i - 1]
if prime[i] == true {
// When current element is prime
this.primeCount[i] = this.primeCount[i] + 1
}
}
}
func(this PrimeCounting) primeBetween(a, b int) {
var result int = 0
if a > 0 && b > 0 {
if a >= this.limit || b >= this.limit {
// When range are outside the limit
return
}
result = this.primeCount[b] - this.primeCount[a]
}
fmt.Print("\n Prime between (", a, ",", b, ") ")
fmt.Print("\n Result : ", result)
}
func main() {
var task * PrimeCounting = getPrimeCounting()
/*
prime number between 25-100
[
29  31  37  41  43  47  53  59  61
67  71  73  79  83  89  97
]
Result = 26

*/
/*
prime number between 1000-1200
[
1009  1013  1019  1021  1031  1033  1039
1049  1051  1061  1063  1069  1087  1091
1093  1097  1103  1109  1117  1123  1129
1151  1153  1163  1171  1181  1187  1193
]
Result = 28
*/
}``````

#### Output

`````` Prime between (25,100)
Result : 16
Prime between (1000,1200)
Result : 28``````

## Resultant Output Explanation

The program prints the prime numbers between the given ranges, along with the resulting count.

For example:

1. primeBetween(25, 100):

• The prime numbers between 25 and 100 are [29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97].
• The resulting count is 16.
2. primeBetween(1000, 1200):

• The prime numbers between 1000 and 1200 are [1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193].
• The resulting count is 28.

## Time Complexity of the Code

The time complexity of the code is O(n log(log n)), where n is the limit of prime numbers. This is due to the implementation of the Sieve of Eratosthenes algorithm, which eliminates multiples of primes up to the square root of the limit.

## Finally

Counting prime numbers between two given numbers is efficiently solved using the Sieve of Eratosthenes algorithm. The Java program provided in this article demonstrates an implementation of this algorithm and calculates the count of prime numbers between the specified ranges. Understanding the logic and time complexity of the code helps in solving similar problems efficiently.

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