icancode.de

Ein Sieb für Primzahlen

Einleitung

Rico Magnucki

Rico Magnucki

21st Century Digital Boy und Blog-Gründer. Studiert naturwissenschaftliche Informatik in Bielefeld. Auf dem Blog ist er der Ansprechpartner für LaTeX, schreibt Tutorials, dreht die Videos für YouTube und durchforstet das Internetz nach spannenden Dingen.


Neuste Artikel

HP Deskjet 3636 – Multitalent zum schmalen Preis 09th April, 2017

NETGEAR AC1750 Smart WLAN-Router im Test 10th January, 2016

Allgemein

Ein Sieb für Primzahlen

Veröffentlicht am .

Primzahlen finden eine breite Anwendung in der Informatik. Dabei handelt es sich um Zahlen, die nur durch 1 und sich selbst teilbar sind. So z.B. 3, 5, 7, 13…

In diesem kleinen Bereich ist es noch relativ einfach, Zahlen als Primzahlen zu identifizieren. Wird der Wertebereich größer, ist es ein ziemlich aufwendiges Unterfangen. Was können wir also tun, um die Suche zu beschleunigen?

Das Sieb des Eratosthenes von Kyrene

Die Idee ist genau so einfach, wie sie genial ist. Aus einer Reihe von Zahlen werden nach und nach alle vielfachen des Laufindexes rausgestrichen – was dabei nicht aus der Liste fliegt, muss also eine Primzahl sein.

Programmiertechnisch könnte man das z.B. so umsetzen:

@NotNull
fun lambdaPrimesTill(a: Int): ArrayList {
    var inputRange = (2..a).toArrayList()
    (2..a + 1).forEach { n -> inputRange.removeAll((2*n..a).filter { it % n == 0 }) }
    return inputRange
}

Das ist jetzt zwar schön kurz, aber alles andere als lesbar. Lösen wir die Lambdas also mal auf und schauen uns das genauer an. Diesmal ohne verschachtelte Lamdbas und mit expliziter Typdeklaration.

@NotNull
fun primesTill(a: Int): ArrayList {
    var inputRange: ArrayList = (2..a).toArrayList()
    for (n: Int in 2..a + 1) {
        inputRange.removeAll(
                (2 * n..a)
                        .filter { it: Int ->
                            it % n == 0
                        })
    }
    return inputRange
}

Was passiert hier?
Zuerst wird eine ArrayList erstellt, die mit den Werten 2 bis input+1 gefüllt wird. 0 und 1 sind per Definition keine Primzahlen, demnach reicht es, wenn die Liste bei 2 startet.
Anschließend wird durch die Liste iteriert. Für jede Zahl die wir im Iterator haben, entfernen wir alle Vielfachen aus der Liste. In meinem Fall nutze ich dafür einen filter. Dieser bekommt als Condition ein Lambda. Ist der Iterator beispielsweise bei 2 würde der Rückgabewert des Filters eine Liste von allen Vielfachen von 2 sein.
Dabei sei kurz angemerkt, dass dies sicherlich nicht die performanteste Lösung ist, aber die anschaulichste, wie ich finde.

Wollt ihr jetzt wissen, ob eine gegebene Zahl eine Primzahl ist, könnt ihr einfach nachgucken, ob sie in dieser Liste enthalten ist.
Bei dieser Methode ist übrigens auch zu beachten, dass der Input vorher validiert werden sollte. So wie oben beschrieben, funktioniert das nur mit positiven, geraden Zahlen >= 2 – ansonsten bekommt ihr eine leere Liste zurück. Negative Zahlen sind ja schließlich auch keine Primzahlen ;)

Rico Magnucki

Rico Magnucki

http://magnucki.de

21st Century Digital Boy und Blog-Gründer. Studiert naturwissenschaftliche Informatik in Bielefeld. Auf dem Blog ist er der Ansprechpartner für LaTeX, schreibt Tutorials, dreht die Videos für YouTube und durchforstet das Internetz nach spannenden Dingen.

Navigation