Zurück

Sieve of Eratosthenes using HashSet

Prime numbers are computed using Eratosthenes' algorithm and HashSet. Integer.MAX_VALUE was chosen to provoke a memory consumption failure.

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

/**
 * Das Sieb des Eratosthenes implementiert mit HashSet
 *
 * @author neubauer 14.10.2022 create
 */
public class HashSieb
{
    private static final int N = Integer.MAX_VALUE;
    private static final int START = 2;
    private static Map<Integer, HashSet<Integer>> zahlenZuTeilern = new HashMap<Integer, HashSet<Integer>>();
    private static Map<Integer, Integer> redundanteZugriffe = new HashMap<Integer, Integer>();

    public static void main(final String[] args)
    {
        initMaps();
        fillMapsNotRedundant();
        outputResults();
        initMaps();
        fillMapsRedundant();
        outputResults();
    }

    private static void outputResults()
    {
        if (!redundanteZugriffeVorhanden())
        {
            zahlenZuTeilern.forEach((zahl, teilerSet) -> {
                System.out.print(zahl + " hat folgende Teiler:\t");
                teilerSet.forEach((teiler) -> {
                    System.out.print(teiler + "\t");
                });
                System.out.println("");
            });
            System.out.println(". . . . . . . . . ");
            System.out.println("Es gab keine redundanten Schreiboperationen.");
        }
        else
        {
            System.out.println("Es wurden folgende Primzahlen ermittelt:");
            zahlenZuTeilern.forEach((zahl, teilerSet) -> {
                if (teilerSet.contains(1))
                {
                    System.out.print(zahl + " ");
                }
            });
            System.out.println("");
        }
    }

    private static boolean redundanteZugriffeVorhanden()
    {
        boolean result = false;
        for (int i = START; i < redundanteZugriffe.size(); i++)
        {
            if (redundanteZugriffe.get(i) > 0)
            {
                result = true;
                break;
            }
        }
        return result;
    }

    private static void fillMapsNotRedundant()
    {
        for (int i = START; i < N; i++)
        {
            for (int j = START; j < (i / 2); j++)
            {
                if (i % j == 0)
                {
                    if (zahlenZuTeilern.get(i).contains(j))
                    {
                        int r = redundanteZugriffe.get(i);
                        redundanteZugriffe.put(i, r++);
                    }
                    else
                    {
                        zahlenZuTeilern.get(i).add(j);
                    }
                }
            }
        }
    }

    private static void fillMapsRedundant()
    {
        for (int h = START; h < N; h++)
        {
            zahlenZuTeilern.get(h).add(1); // "true"
        }
        for (int i = START; i < N; i++)
        {
            // die Auskommentierung erzeugt die redundanten Aufrufe:
//            if (zahlenZuTeilern.get(i).contains(1))
//            {
            int temp = i;
            do
            {
                temp += i;
                if (temp < N)
                {
                    if (zahlenZuTeilern.get(i).contains(0))
                    {
                        redundanteZugriffe.put(i, redundanteZugriffe.get(i) + 1);
                    }
                    zahlenZuTeilern.get(temp).clear();
                    zahlenZuTeilern.get(temp).add(0); // ist keine Primzahl ("false")
                }
            }
            while (temp < N);
//            }
        }
    }

    private static void initMaps()
    {
        zahlenZuTeilern.clear();
        redundanteZugriffe.clear();
        for (int h = 2; h < N; h++)
        {
            zahlenZuTeilern.put(h, new HashSet<Integer>());
            redundanteZugriffe.put(h, 0);
        }
    }

}