Skip to main content

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)
	{
		PrimeCounting task = 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
		    
		*/
		task.primeBetween(25, 100);
		/*
		    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
		*/
		task.primeBetween(1000, 1200);
	}
}

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()
{
    PrimeCounting *task = 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
        
    */
    task->primeBetween(25, 100);
    /*
        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
    */
    task->primeBetween(1000, 1200);
    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)
	{
		PrimeCounting task = 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
		    
		*/
		task.primeBetween(25, 100);
		/*
		    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
		*/
		task.primeBetween(1000, 1200);
	}
}

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()
{
	$task = 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
	    
	*/
	$task->primeBetween(25, 100);
	/*
	    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
	*/
	$task->primeBetween(1000, 1200);
}
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()
{
	var task = 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
	    
	*/
	task.primeBetween(25, 100);
	/*
	    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
	*/
	task.primeBetween(1000, 1200);
}
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() :
	task = PrimeCounting()
	#    prime number between 25-100
	#    [
	#        29  31  37  41  43  47  53  59  61  
	#        67  71  73  79  83  89  97
	#    ]
	#    Result = 26
	task.primeBetween(25, 100)
	#    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
	task.primeBetween(1000, 1200)

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_reader :limit, :primeCount
	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() 
	task = PrimeCounting.new()
	#    prime number between 25-100
	#    [
	#        29  31  37  41  43  47  53  59  61  
	#        67  71  73  79  83  89  97
	#    ]
	#    Result = 26
	task.primeBetween(25, 100)
	#    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
	task.primeBetween(1000, 1200)
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
		    
		*/
		task.primeBetween(25, 100);
		/*
		    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
		*/
		task.primeBetween(1000, 1200);
	}
}

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()
{
	let task: PrimeCounting = PrimeCounting();
	/*
	    prime number between 25-100
	    [
	        29  31  37  41  43  47  53  59  61  
	        67  71  73  79  83  89  97
	    ]
	    Result = 26
	    
	*/
	task.primeBetween(25, 100);
	/*
	    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
	*/
	task.primeBetween(1000, 1200);
}
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
{
	val task: PrimeCounting = PrimeCounting();
	/*
	    prime number between 25-100
	    [
	        29  31  37  41  43  47  53  59  61  
	        67  71  73  79  83  89  97
	    ]
	    Result = 26
	    
	*/
	task.primeBetween(25, 100);
	/*
	    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
	*/
	task.primeBetween(1000, 1200);
}

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
	    
	*/
	task.primeBetween(25, 100)
	/*
	    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
	*/
	task.primeBetween(1000, 1200)
}

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.

Last updated on by Kalkicode




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