Skip to content

Count Primes (Sieve of Eratosthenes)

Count Primes (Sieve of Eratosthenes): A Comprehensive Guide

Finding the number of prime numbers less than a given non-negative integer can be a challenging task. However, with the right algorithm, this task becomes much simpler. In this article, we will explore the “Count Primes” problem and implement the Sieve of Eratosthenes, an efficient algorithm to solve it. Through this guide, we will break down the algorithm step-by-step, discuss its implementation in Java, and provide useful resources for further learning.

Understanding the Problem

The objective of the Count Primes problem is to determine how many prime numbers exist that are less than a given number n. For instance, if we take n = 10, the prime numbers less than 10 are 2, 3, 5, and 7, resulting in a total of 4 prime numbers.

To illustrate further:

  • If n = 0, the result is 0 since there are no prime numbers.
  • If n = 1, the result is again 0 for the same reason.

Introduction to the Sieve of Eratosthenes

The Sieve of Eratosthenes is a classic algorithm used to find all prime numbers up to a specified integer. It efficiently identifies prime numbers by iteratively marking the multiples of each prime starting from 2. The numbers that remain unmarked at the end of the process are the prime numbers.

How the Algorithm Works

Let’s take a closer look at how the Sieve of Eratosthenes operates:

  1. Start with an array of boolean values, initialized to false, indicating that all numbers are initially considered prime.
  2. Mark 1 as true (not prime).
  3. Begin with the first prime number, 2, and mark all of its multiples (i.e., 4, 6, 8, …) as true.
  4. Move to the next number that is still false and repeat the marking process for its multiples.
  5. Continue this process until you reach the square root of n.
  6. Count the numbers that remain marked as false, which represent the prime numbers.

Implementing the Sieve of Eratosthenes in Java

Now that we have a solid understanding of the algorithm, let’s implement it in Java. Below is a step-by-step guide to writing the code.

Step 1: Set Up the Method

We will create a method called countPrimes that takes an integer n as input and returns the count of prime numbers less than n.

public int countPrimes(int n) {
    if (n <= 2) return 0; // No primes less than 2
    boolean[] isPrime = new boolean[n];
    Arrays.fill(isPrime, true); // Assume all numbers are prime
    isPrime[0] = isPrime[1] = false; // 0 and 1 are not primes
    // Continue with the algorithm
}

Step 2: Implement the Sieve Logic

Next, we will implement the logic to mark non-prime numbers.

for (int i = 2; i * i < n; i++) {
    if (isPrime[i]) {
        for (int j = i * i; j < n; j += i) {
            isPrime[j] = false; // Mark multiples of i as non-prime
        }
    }
}

Step 3: Count the Primes

Finally, we will count the number of primes that remain marked as false.

int count = 0;
for (boolean prime : isPrime) {
    if (prime) count++;
}
return count;

Complete Code

Here’s the complete Java code for the countPrimes method:

import java.util.Arrays;

public class PrimeCounter {
    public int countPrimes(int n) {
        if (n <= 2) return 0; // No primes less than 2
        boolean[] isPrime = new boolean[n];
        Arrays.fill(isPrime, true); // Assume all numbers are prime
        isPrime[0] = isPrime[1] = false; // 0 and 1 are not primes

        for (int i = 2; i * i < n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j < n; j += i) {
                    isPrime[j] = false; // Mark multiples of i as non-prime
                }
            }
        }

        int count = 0;
        for (boolean prime : isPrime) {
            if (prime) count++;
        }
        return count;
    }
}

Time and Space Complexity

The time complexity of the Sieve of Eratosthenes is O(n log log n), which makes it efficient for large values of n. The space complexity is O(n) due to the boolean array used to track prime numbers.

Further Learning Resources

To enhance your understanding of data structures and algorithms, consider exploring the following resources:

Conclusion

The Count Primes problem is a great way to understand the Sieve of Eratosthenes algorithm and its application in counting prime numbers. By following the steps outlined in this guide, you can efficiently determine the number of primes less than any non-negative integer. Keep practicing, and don’t hesitate to explore additional resources to deepen your knowledge in algorithms!

Thank you for reading, and happy coding!

Algorithms made easy