001    package de.hska.java.aufgaben.kontrollstrukturen;
002    /**
003     * Berechnen der ersten n Primzahlen mit dem Sieb des Eratosthenes.
004     * 
005     * 
006     * @author Christian Pape
007     */
008    public class Primzahlsieb {
009    
010        private boolean[] sieb;
011    
012        /**
013         * Erzeugt ein Primzahlsieb, mit dem alle Primzahlen
014         * von 1 bis n berechnet werden können.
015         * 
016         * @param n eine positive Zahl, größer 1
017         */
018        public Primzahlsieb(int n) {
019            sieb = new boolean[n + 1];
020        }
021    
022        /**
023         * Berechnet alle Primzahlen von 1 bis zu einer Obergrenze.
024         * Zeitaufwand ist O(n log log n).
025         * Speicheraufwand O(n).
026         */
027        public void primzahlenBerechnen() {
028            for (int p = 2; p < sieb.length; p++) {
029                sieb[p] = true;
030            }
031    
032            for (int p = 2; p < sieb.length; p++) {
033                if (sieb[p]) {
034                    for (int i = 2 * p; i < sieb.length; i += p) {
035                        sieb[i] = false;
036                    }
037                }
038            }
039        }
040    
041        /**
042         * Gibt alle Primzahlen von n - 100 bis n aus.
043         */
044        public void primzahlenAusgeben() {
045            for (int p = sieb.length - 100; p < sieb.length; p++) {
046                if (sieb[p]) {
047                    System.out.println(p);
048                }
049            }
050        }
051    
052        /**
053         * Gibt genau dann true zurück, wenn p eine Primzahl ist.
054         * Bevor diese Methode aufgerufen wird, muss
055         * {@link #primzahlenBerechnen} einmal aufgerufen werden.
056         */
057        public boolean isPrim(int p) {
058            return sieb[p];
059        }
060    
061    }