Home Tutorials Training Consulting Products Books Company Donate Contact us









NOW Hiring

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. About this website

4. Links and Literature

Not listed yet.

4.3. vogella GmbH training and consulting support

TRAINING SERVICE & SUPPORT

The vogella company provides comprehensive training and education services from experts in the areas of Eclipse RCP, Android, Git, Java, Gradle and Spring. We offer both public and inhouse training. Whichever course you decide to take, you are guaranteed to experience what many before you refer to as “The best IT class I have ever attended”.

The vogella company offers expert consulting services, development support and coaching. Our customers range from Fortune 100 corporations to individual developers.

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

See Licence.