Home Tutorials Training Consulting Books Company Contact us

Get more...

Training Events

Abstract. This article describes the calculation of prime numbers with the sieve of Eratosthenes in Java

1. Prime Factorization

A prime is an integer greater than one whole only positive divisors are one and itself.

The prime counting function for a number N (also known as pie(N)) is the number of primes less or equal to N. The following algorithm determines all prime numbers until a certain value.

2. Implementation in Java

Create a Java project "de.vogella.algorithms.primenumbers".

Create the following program.

package de.vogella.algorithms.primenumbers;

import java.util.ArrayList;
import java.util.List;

// Using the sieve of Eratosthenes
public class PrimeNumbers {
    public static List<Integer> calcPrimeNumbers(int n) {
        boolean[] isPrimeNumber = new boolean[n + 1]; // boolean defaults to
        // false
        List<Integer> primes = new ArrayList<Integer>();
        for (int i = 2; i < n; i++) {
            isPrimeNumber[i] = true;
        for (int i = 2; i < n; i++) {
            if (isPrimeNumber[i]) {
                // now mark the multiple of i as non-prime number
                for (int j = i; j * i <= n; j++) {
                    isPrimeNumber[i * j] = false;


        return primes;

    public static void main(String[] args) {
        List<Integer> calcPrimeNumbers = calcPrimeNumbers(21);
        for (Integer integer : calcPrimeNumbers) {
        System.out.println("Prime counting function (Pie(N)) : "
                + calcPrimeNumbers.size());

3. Links and Literature

Nothing listed.

If you need more assistance we offer Online Training and Onsite training as well as consulting

Legal Privacy Policy Change consent