Java: Count the number of prime numbers less than a given positive number

Last update on May 15 2025 13:08:35 (UTC/GMT +8 hours)

Count Primes Below Number

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

Sample Solution:

Java Code:

import java.util.*;
 public class Example12 {
 public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        System.out.print("Input an integer: ");
		int x = in.nextInt(); 
		System.out.print("The number of prime numbers: "+countPrimes(x));
		System.out.printf("\n");
	}

       public static int countPrimes(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 s = (int)Math.sqrt(n);
        int ctr = n;
        for(int p = 2; p <= s; p ++)
        {
            if(!set.get(p))
            {
                for(int q = 2; (p * q) <= n; q ++)
                {
                    if(!set.get(p * q))
                    {
                        ctr --;
                        set.set(p * q);
                    }
                }
            }
        }
        return ctr - 1;
    }        
 }

Sample Output:

Input an integer: 25                                                   
The number of prime numbers: 9    

Flowchart:

For more Practice: Solve these Related Problems:

• Write a Java program to count the number of prime numbers less than a given number using the Sieve of Eratosthenes.
• Write a Java program to count primes below a number using recursion with memoization.
• Write a Java program to count primes by filtering a range with Java streams and lambda expressions.
• Write a Java program to implement a segmented sieve algorithm and compare its prime count with the classic sieve.

Go to:

• Java Math Exercises Home ↩
• Java Exercises Home ↩

PREV : Check for 15 Condition.
NEXT : Count Primes Below Number.

Java Code Editor:

Contribute your code and comments through Disqus.