w3resource

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


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:

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



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:


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


Java Code Editor:

Contribute your code and comments through Disqus.

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.



Follow us on Facebook and Twitter for latest update.