Der Kiebart-Kamm ist ein alternatives Verfahren zum Sieb des Eratosthenes um die Nichtprimzahlen innerhalb eines vorgegebenen Zahlenbereichs zu markieren. Genau wie beim Eratosthenes-Sieb sind die nicht markierten Zahlen die Primzahlen. 

Der Vorteil beim Kiebart-Kamm liegt darin, dass jede Nichtprimzahl genau einmal (und nicht mehrfach) markiert wird. Dadurch gewinnt dieses Verfahren enorm an Geschwindigkeit. Dass dies so ist, zeigt ein Rechenbeispiel mit 1.000.000.000 Zahlen. In diesem Bereich sind ca. 50 Millionen Primzahlen enthalten. Markiert werden müssen also mindestens 950 Millionen Zahlen. Wenn dies, wie mit dem Kiebart-Kamm allein durch das Verfahren gelingt, hat man das Optimum erreicht und kann dies nur noch dadurch toppen, dass man das Markierungsverfahren so ändert, dass die 50 Millionen Primzahlen statt der 950 Millionen Nichtprimzahlen markiert werden. Sascha Pfaller benötigt für sein Verfahren ebenfalls nicht so viele mehrfache Markierungen wie der ehrwürdige Eratosthenes. Das Sieb vom Eratosthenes streicht zum Beispiel die NichtPrimzahl  323.323 = 7 x 11 x 13 x 17 x 19 exakt 5 mal (Dies ist ein Extremfall). Aber auch dieses Sieb hat Optimierungsmöglichkeiten und kann zumindest theoretisch sogar bis zum Kiebart-Kamm optimiert werden, der ja - ich wiederhole mich - jede Nichtprimzahl nur einmal trifft.

Erklärungen zum Kiebart-Kamm:

Wir gehen davon aus, dass beim Start des Kämmens alle Zahlen >1 Primzahlen sind. Die erste Primzahl ist dann die 2 und die folgende Primzahl die 3. Wir streichen das Produkt (6 = 2*3) und kennzeichnen die 6 als Nicht-Prim.

Wir werden sehen, dass die Quadratzahlen im ersten Siebschritt eine besondere Bedeutung einnehmen und teilweise als Primzahlen erhalten bleiben. Aber - keine Sorge - diese Unzulänglichkeit wird im 2. Schritt wieder wettgemacht.

Beim Streichen des nächst möglichen Produkts (Primzahl 2 * "Primzahl" 4) streichen wir die 8. Dann 2*5 =10 

2*6=12 wird nicht durchgeführt, da 6 als Nicht-Prim entlarvt wurde. Hinweis: Dies wird später durch 3*4 gemacht.

Wir fahren mit folgenden Streichungen fort: 2*7; 2*9; 2*11; 2*12; 2*13 usw.

Viele - aber nicht alle - der geraden Zahlen wurden nun bereits entfernt und damit als Nicht-Prim markiert. 

Nun wiederholen wir in einer Schleife das Verfahren für die nächste Primzahl (3) und starten mit dem Produkt 3*4. Zur Erinnerung: 4 gilt immer noch als Primzahl! - Wir streichen also die 12

Danach 3*5; 3*7 (6 ist keine Primzahl mehr - Sie wurde im 1. Durchlauf gestrichen; ebenso die 8); 3*9; 3*11; Da die 12 just entfernt wurde, folgt: 3*13; 3*16 usw. für alle 3er-Produkte mit "Noch-Primzahlen"

Die nächste Schleife ist der (noch nicht gestrichenen) 4 gewidmet. Auch die 4 wird mit mit allen folgenden Noch-Primzahlen multipliziert und die Produkte gestrichen: 4*5; 4*7; 4*9; 4*11 usw.

Die 5er-Schleife startet mit 5*7; 5*9; 5*11; 5*13; 5*17

Da die 6 keine Primzahl mehr ist, folgt die 7er-Schleife usw......

Das Resultat aller Schleifen ist ein Primzahlenblock, der aber noch Quadratzahlen enthält. Diese werden im letzten Schritt entfernt.

------------------------------------------------------------------------------------------------------------

Optimieren kann man das Verfahren des Kiebart-Kamms folgendermaßen:

Man entfernt vorab alle durch 2, 3, 5 teilbare Zahlen aus dem zukünftigen Primzahlenblock und erhält eine Liste von 8 Zahlen:

1; 7; 11; 13; 17; 19; 23; 29

Dieses 30er-Muster (2*3*5=30) wiederholt sich im gesamten Primzahlenblock, indem man ein beliebiges Vielfaches von 30 hinzuaddiert.

Optimiertes Verfahren Kiebart-Kamm.

Die 1 wird als Nicht-Prim markiert!

1. Primzahl ist nun die 7, 2. Primzahl die 11

7*11 = 77 wird gestrichen, ebenso 7*13; 7*17; 7*19; 7*23; 7*29; 7*31; 7*37 usw. Mit dabei ist auch 7*49!!! und 7*121

Es folgt die Schleife für 11, die bei 11*13 startet.

Am Schluss werden wieder die Quadratzahlen entfernt.

Die drei Primzahlen 2, 3, 5 sind nicht gespeichert und müssen gesondert behandelt werden. Bei der Speicherung empfiehlt sich eine 8Bit-Speicherung pro 30er-Zahlenblock. So lässt sich eine große Menge an Primzahlen auf kleinstem Raum speichern.

------