Write a Java program to count the number of prime numbers less than a given positive number


This Java program counts the number of prime numbers less than or equal to the input number. The count_primes() method takes an integer n as input and returns the number of prime numbers less than or equal to n. It uses the Sieve of Eratosthenes algorithm to generate a list of prime numbers up to n, and counts the number of primes found.

The program first checks if the input number is less than or equal to 0 or equal to 1 or 2, in which case there are no prime numbers less than or equal to it. If the input number is equal to 3, then there is only one prime number less than or equal to it (2). Otherwise, the program proceeds to generate a list of primes.

The program uses a BitSet to mark off composite numbers (i.e., non-prime numbers) as it generates them. It starts by setting n to n-1, since it is looking for prime numbers less than or equal to n. It then loops through all integers from 2 up to the square root of n, marking off all multiples of each integer as composite. The loop uses the get() method to check if a number is already marked as composite, and the set() method to mark a number as composite. The program then returns the number of primes found, which is equal to the number of integers less than or equal to n minus the number of composites found.

Source Code

import java.util.*;
 public class Count_PrimeNumbers
{
	public static void main(String[] args)
	{
		Scanner input = new Scanner(System.in);
		System.out.print("Enter a Number : ");
		int num = input.nextInt(); 
		System.out.print("Number of Prime Numbers : "+count_primes(num));
	}
	public static int count_primes(int n)
	{
		if(n <= 0 || n == 1 || n == 2) 
			return 0;
		else if(n == 3)
			return 1;
		BitSet set = new BitSet();
		n = n - 1;
		int sq = (int)Math.sqrt(n);
		int c = n;
		for(int x = 2; x <= sq; x ++)
		{
			if(!set.get(x))
			{
				for(int y = 2; (x * y) <= n; y ++)
				{
					if(!set.get(x * y))
					{
						c --;
						set.set(x * y);
					}
				}
			}
		}
		return c - 1;
	}
 }

Output

Enter a Number : 10
Number of Prime Numbers : 4

Example Programs