Skip to main content

Count prime numbers between two numbers

Here given code implementation process.

// 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
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