Das Kontraxiom
Der
Kiebartkamm / Sieb des KiebartDieses
Sieb markiert jedes Bit als Nicht-Primzahl genau einmal und
man erhält eine Liste aller Primzahlen bis zu einer vorgegebenen
Grenze.
|
|
Innerhalb eines BitArrays wird jedem Byte ein Zahlenbereich von
30 fortlaufenden Zahlen zugeordnet. Gespeichert werden die Mod 30
Reste:
1, 7, 11, 13, 17, 19, 23, 29.
Die Primzahlen 2, 3, 5 werden nicht gespeichert, ebenso wie alle
Vielfachen dieser Zahlen in dieser Speicherung fehlen.
| |
Bit 0 |
Bit 1 |
Bit 2 |
Bit 3 |
Bit 4 |
Bit 5 |
Bit 6 |
Bit 7 |
|
Byte 0 |
1 |
7 |
11 |
13 |
17 |
19 |
23 |
29 |
|
Byte 1 |
31 |
37 |
41 |
43 |
47 |
49 |
53 |
59 |
|
Byte 2 |
61 |
67 |
71 |
73 |
77 |
79 |
83 |
89 |
|
Byte 3 |
91 |
97 |
101 |
103 |
107 |
109 |
113 |
119 |
1. Alle Zahlen (bis auf die 1) werden als Prim markiert.
FOR P1 = 7 TO Wurzel(Grenze) (Nur für Bits, die noch Prim sind)
FOR P2 = >P1 TO Grenze (Nur für
Bits, die noch Prim sind)
ERG = P1 *
P2
/* Erstes Produkt ist 7 * 11 = 77 */
IF ERG
> GRENZE THEN EXIT FOR
Bit für
ERG auf Nicht-Prim setzen
NEXT P2
NEXT P1
FOR P3 = Wurzel(Grenze) TO 7 STEP –1 (Nur für Bits, die noch
Prim sind)
Quadrat = P3 * P3
Bit für Quadrat auf Nicht-Prim setzen
NEXT P3
|
