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

Java Math Exercises: Exercise-12 with Solution

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:

Java Code Editor:

Contribute your code and comments through Disqus.

Previous: Write a Java program to accept two integers and return true if the either one is 15 or if their sum or difference is 15.
Next: Write a Java program to find the length of the longest sequence of zeros in binary representation of an integer.