Home Tutorials Training Consulting Products Books Company Donate Contact us









Online Training

Quick links

Share

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

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]) {
                primes.add(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(integer);
        }
        System.out.println("Prime counting function (Pie(N)) : "
                + calcPrimeNumbers.size());
    }
}
-->

Copyright © 2012-2018 vogella GmbH. Free use of the software examples is granted under the terms of the Eclipse Public License 2.0. This tutorial is published under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Germany license.

See Licence.