Home Tutorials Training Consulting Products Books Company Donate Contact us









Online training

Events

Quick links

Share

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]) {
                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());
    }
}

3. Links and Literature

Nothing listed.

4. vogella training and consulting support

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.