Wie man den Algorithmus effizient umsetzt
Die hier Vorgestellten Optimierungen beziehen sich auf den Algorithmus und sind unabhängig von der Programmiersprache.
Sieb von Atkin kurz erklärt
Das Sieb von Atkin verwendet die drei Gleichungen
4x2 + y2 = P
wobei P = 1, 13, 17, 29, 37, 41, 49, oder 53 mod 60
3x2 + y2 = P
wobei P = 7, 19, 31 oder 43 mod 60
3x2 – y2 = P
wobei P = 11, 23, 47 oder 59 mod 60 und x > y
zur Bestimmung von Primzahlen. Besitzt eine Zahl P für eine dieser Gleichungen eine ungerade Anzahl Lösungen, dann ist P entweder eine Primzahl oder besitzt quadratische Teiler.
Man erstellt eine Liste mit einem Eintrag für jede positive ganze Zahl bis zum gewünschten Limit mit einem Schalter für „prim“/“nicht prim“. Dieser steht standardmäßig auf „nicht prim“.
Für jede gefundene Lösung mit erlaubtem Modulo schaltet man den Schalter um.
Nur Primzahlen und Zahlen, die quadratische Teiler besitzen sind jetzt auf „prim“ geschaltet. Man geht die Liste der auf „prim“ gesetzten Zahlen durch, quadriert sie und schaltet alle Vielfachen des Quadrates auf „nicht prim“.
Die Primzahlen 2 , 3 und 5 haben hier keine Lösung und werden in der Liste ergänzt.
Vergl. mit dem Wikipedia-Artikel zum Sieb von Atkin
Die theoretische Funktionsweise des Algorithmus ist vergleichsweise einfach. Für eine effiziente Umsetzung sind jedoch zusätzliche Optimierungen notwendig, da ein großer Teil der Berechnungen unnötige Werte erzeugt.
.
Optimierungen des Atkin-Siebs
Bei mod 60 wie im Pseudocode werden viele n berechnet, die dann ohnehin nicht invertiert werden. Anstatt die Werte n zu filtern, kann man den Suchraum auf nur gültige Werte einschränken.
Quadratschritt nur für invertierte Werte
Weil keine durch 2 oder 3 teilbaren Werte n invertiert wurden, muss für diese die Quadratfreiheit nicht geprüft werden. Berechne n2 und 5n2 und markiere beide als nicht prim. Erhöhe beide immer wieder um 6n2.
Nur gültige Lösungen mod 12 erzeugen
Wie Auf der Seite „Erklärung“ erwähnt lassen sich n gut nach x und y sortieren. Anstatt x und y brute force zu nehmen, beschränkt man x und y auf die Werte, die in Kombination ein gültiges n ergeben.
Die vielen Kombinationsmöglichkeiten von x und y bei modulo 60 machen das Sieb nicht effizienter. Man braucht mindestens doppelt so viele Schleifen, das führt zu vielen Doppelberechnungen von x und y. Man kann den Teiler 5 auch anders ausschließen. Dazu später mehr.
Mod 12 ist hier zunächst besser geeignet. Man berechnet mit
4x2 + y2 nur Lösungen, die 1 oder 5 mod 12 ergeben,
mit 3x2 + y2 nur Lösungen ,die 7 mod 12 ergeben.
und mit 3x2 – y2 nur Lösungen, die 11 mod 12 ergeben.
Auch hier entspricht x den Zeilenüberschriften und y den Spaltenüberschriften. x und y sind Reste mod 12:
Die kleinstmöglichen Kombinationen sind:
Für 4x2 + y2 = 1 oder 5 mod 12:
x = 0, 1 mod 2 mit y =1, 5 mod 6 und x = 1, 2 mod 3 mit y = 3 mod 6
Für 3x2 + y2 = 7 mod 12:
x = 1 mod 2 mit y = 2, 4 mod 6
Für 3x2 – y2 = 11 mod 12:
x = 1 mod 2 mit y =2, 4 mod 6 und x = 0 mod 2 mit y = 1, 5 mod 6
1 mod 12 wird sowohl mit 3x2 + y2 als auch mit 4x2 + y2 gelöst. Beschränkt man x und y, dann fällt diese Redundanz weg. Diese Optimierung wirkt also am meisten bei Gl. 2. Man muss n nicht mehr auf Restklassen modulo 12 prüfen, weil nur gültige Werte n erzeugt werden. Nur rund 1/3 der Lösungen wird berechnet. Der Quadratschritt beginnt mit 52.
Maximum für x
Man kann die Anzahl der Lösungen noch weiter beschränken, indem man für jede Gleichung ein Maximum für x festlegt (Limit = größter Eintag):
Bei Gl . 1: 4x2 + y2:
x max = (Limit/4)0,5.
Bei Gl. 2: 3x2 + y2:
x max = (Limit/3)0,5.
Bei Gl. 3: 3x2 – y2:
x max = (Limit/2)0,5 (das entspricht (1,5*Limit/3)0,5. Siehe kleinstes erlaubtes Verhältnis in der Tabelle)
Maximum für y bei Gl. 1 und Gl. 2
y max ist bei Gl. 1 und Gl. 2 erreicht, wenn n > Limit. y beschränkt man also mit der Bedingung: Wenn n > Limit, brich ab. Gehe zum nächsten x.
y start für 3x2 – y2
Bei Gl. 3 gilt x > y. 3x2 geht bis 1,5*Limit. Hier entstehen Werte n größer als Limit, sobald 3x2 größer als Limit ist, denn je kleiner y desto größer ist n. Man kann einen dynamischen Startwert für y festlegen und ihn dann für jedes x ggf. nach oben korrigieren: Wenn n > Limit, dann ist das aktuelle y das neue y start für das nächste x.
Benchmark für 3x2 – y2 mit und ohne y start
Die Tabelle zeigt die Anzahl n größer Limit bei Gl. 3 und die Zeit ohne und mit y start. Die verbleibenden n größer als Limit entstehen mit der Bedingung: Wenn n größer Limit ist, dann erhöhe y start.
Anm.: Die Zeitangaben in allen Benchmarks schwanken bei jedem Start des Programms, sie sind also nur Richtwerte)
Weitere Optimierungen bei höheren Limits
y start für alle drei Gleichungen
Will man ein segmentiertes Sieb bauen, dann ist y start auch für Gl. 1 und 2 sinnvoll. Man beginnt bei x = 1 und y max und rechnet mit x aufwärts und y abwärts. Das stellt sicher, dass sich y und y start in die gleiche Richtung ändern. Das erste y start muss auf korrekten Rest mod 6 gesetzt werden.
Mod 60 ohne Modulo – nur über x/y Beschränkung
Bei Gl. 1 sind viele n durch 5 teilbar. Diese kann man vorab ausschließen, indem man x und y mod 5 berechnet. Wenn dann x + y = 5 oder x – y = 0, oder besser nur vergleichen, wenn x/y = 0/0 oder 1, 4/1, 4 oder 2, 3/2, 3, dann ist y ungültig. Weiter mit nächstem y. Das kann man bei mod 120 gut nachrechnen.
Anm.: Das funktioniert bei allen auf der Erklärungsseite vorgestellten Gleichungen, bei denen 5 mit x und y = 1 dargestellt werden kann.
Man kann sehr viele y-mod-5-Prüfungen vermeiden: Nimm y nicht mod 6, sondern mod 30. Schaue, ob die erste xy-Kombination gültig ist, Wenn ja, dann ist auch y + 30 gültig. Erhöhe y in 30er Schritten. Wenn nein, dann Abbruch. (auch y + 30n ist ungültig). Gehe zum nächsten y in der Startliste.
Der Zeit-Vorteil zeigt sich erst ab 1 Million. Man spart Rechenarbeit, aber jede verbleibende Iteration ist teurer – deshalb sieht man den Effekt erst spät. Ca. 36% fallen durch den Filter (9 von 25 xy-Kombinationen).
Die Primzahl 5 wird nicht erzeugt, deshalb muss sie ins Sieb geschrieben werden, damit der Quadratschritt mit 52 beginnt (wegen Gl. 2 und 3).
Bei Gl. 2 und 3 bringt 5n ausschließen fast nichts, der Teiler 5 kommt ohnehin nur als 52 vor, also bei ca. 4% der n. Einzige ungültige Kombination: x mod 5/y mod 5 = 0/0, also 1 von 25. Das wird bei mod 120 sichtbar.
Benchmark mit und ohne Mod-5-Filterung
Die Tabelle zeigt die Laufzeit des gesamten Siebes mit und ohne mod 5 und die Anzahl y, die bei Gl.1 gestartet bzw. übersprungen wird sowie die Gesamtanzahl der benutzten y inkl. +30-Schritte..
x2 und y2 inkrementell berechnen
Man kann x2 und y2 inkrementell berechnen, also aufaddieren anstatt multiplizieren. Das bringt bei großen Limits vermutlich deutlich Speed, ist aber wegen der Restklassen für x und y nicht einfach umzusetzen. Weil man x und y dann nicht kennt, funktioniert hier 5n ausschließen bei Gl. 1 nicht.
Benchmark zum Vergleich der drei Atkin-Gleichungen
Die Tabelle zeigt die Gesamtanzahl der berechneten Werte n und wie viele davon invertiert werden, sowie den Anteil am gesamten Aufwand pro Gleichung mit Limit 1 Million.
Anzahl Primzahlen: 78498
Man sieht: Gl. 3 ist annähernd genauso schnell wie Gl. 2, obwohl es laut Tabelle doppelt so viele x/y-Kombinationen gibt. Gl. 1 löst zwei Reste mod 12, darum hat sie den größten Anteil an Zeit und Treffern.
Weitere Einschränkungen des Algorithmus würden dazu führen, dass gültige Werte n verloren gehen.
Den größten gemeinsamen Teiler ermitteln
Auf der Erklärungsseite ergeben sich folgende Kriterien für Primzahlen:
Eine ganze Zahl P > 3 ist prim, wenn…
- P nicht durch 2 oder 3 teilbar ist,
- Die geeignete Gleichung genau eine positive ganzzahlige Lösung besitzt,
- Und x und y in dieser Lösung keinen gemeinsamen Teiler größer als 1 besitzen.
Der letzte Punkt ist wichtig, da gemeinsame Teiler von x und y quadratische Teiler in n erzeugen.
Der dort beschriebene Test bezieht sich auf die Prüfung einer einzelnen Zahl. Das gleiche Prinzip lasst sich jedoch auch auf größere Zahlenbereiche oder Segmente anwenden.
Dafür müssen Lösungen der Gleichungen gezählt und gleichzeitig gemeinsame Teiler von x und y erkannt werden..
Die folgende Variante erweitert den Primzahltest deshalb zu einer Count-Version für größere Bereiche.
Count-XY Variante
- Erstelle eine Liste mit allen Zahlen für den gewünschten Bereich mit einem Counter mit den möglichen Einträgen: 0, 1, 2. Stelle Count für alle Einträge auf 0.
- Löse die Gleichungen 4x2 + y2 , 3x2 + y2 und 3x2 – y2 mit allen erlaubten Kombinationen von x und y (siehe oben: „Die kleinstmöglichen Kombinationen“:
- Vergl. die Lösungen mit der Liste:
- Wenn Count = 0: Schaue ob x und y einen ggT > 1 haben. Wenn ja, stelle Count auf 2 (sofort ausschließen). Wenn nein, erhöhe Count um 1.
- Wenn Count = 1: Erhöhe ihn um 1.
- Wenn Count = 2: Ignoriere ihn (weitere Lösungen werden nicht gezählt).
- Alle Einträge mit Count = 1 sind Primzahlen.
Auch Lösungen mit x = null müssen ggf. gezählt werden. (Gl 1, erste Schleife) Diese werden zwar durch die ggT-Prüfung auf Count = 2 gesetzt, sie sind aber wichtig für die korrekte Zählung, falls es genau eine weitere Lösung gibt. Bsp.: 4 * 02 + 52 = 25 und 4 * 22 + 32 = 25.
Atkin verwirft diese Fälle beim Quadratschritt, daher darf die Schleife dort mit x = 1 beginnen.
Unterschied zwischen Atkin klassisch und Count Version:
Atkin fragt: „ist die Anzahl der Lösungen ungerade?“ und entfernt Vielfache von Quadraten in einem Extraschritt.
Count-Version fragt: „Gibt es genau eine primitive Lösung?“, und macht direkt den ggT-Test. Weil kein extra Quadratschritt nötig ist, ist diese Version besser segmentierbar. Sie ist jedoch etwas langsamer als ein optimiertes Atkin-Sieb.
Ein Beispielcode zur Visualisierung der optimierten Python-Codes für beide Varianten ist weiter unten angeführt.
Laufzeit-Vergleich der Primzahl-Siebe
Folgende Versionen werden hier verglichen:
- XY-Atkin: x/y optimiert
- Count-XY: x/y optimiert
- Mod60: Original Atkin (Wikipedia) x und y brute force, x max, Abbruch, wenn n > Limit
- Eratosthenes: nicht optimiert
OK: Die Anzahl der gefundenen Primzahlen stimmt überein
Benchmark der verschiedenen Primzahl-Siebe
Die Benchmarks zeigen , dass sich die Laufzeit der optimierten XY-Atkin-Variante im Vergleich zur klassischen Mod-60-Variante halbiert hat.
Warum Eratosthenes schneller bleibt
In den Benchmarks zeigt sich ein überraschendes Ergebnis: Selbst gegenüber einer stark optimierten Atkin-Variante bleibt das Sieb des Eratosthenes etwa doppelt so schnell.
Das wirkt zunächst widersprüchlich, da Atkin theoretisch effizienter ist. Die Ursache liegt jedoch nicht in der Mathematik, sondern in der praktischen Umsetzung auf moderner Hardware.
Weniger Arbeit ≠ schnellere Ausführung
Eratosthenes:
arbeitet streng linear
markiert Vielfache in festen Abständen
Atkin:
erzeugt Treffer abhängig von x und y
verteilt sich unregelmäßig im Speicher
Moderne CPUs sind stark auf lineare Zugriffe optimiert. Das führt dazu, dass Eratosthenes den Cache deutlich effizienter nutzt. Dieser Effekt allein kann bereits einen großen Teil des Geschwindigkeitsunterschieds erklären.
Verzweigungen bremsen Atkin aus
Die Atkin-Formeln enthalten mehrere Bedingungen:
verschiedene Gleichungen
zusätzliche Modulo-Prüfungen
Umschalten (invertieren) von Zuständen
Diese führen zu vielen Verzweigungen im Code.
Eratosthenes dagegen besteht im Kern nur aus:
einer Schleife
einem konstanten Schritt
Weniger Verzweigungen bedeuten:
bessere Vorhersagbarkeit für die CPU
weniger Unterbrechungen der Pipeline
Atkin bleibt rechenintensiv pro Treffer, während Eratosthenes extrem einfache Operationen nutzt.
Für alle typischen Grenzen (bis weit in den Millionen- oder sogar Milliardenbereich) ist der theoretische Vorteil von Atkin nicht groß genug, um die höheren Kosten auszugleichen.
Fazit
Die Benchmarks bestätigen:
Atkin reduziert den Suchraum erfolgreich
die Optimierungen greifen sichtbar
die Laufzeit hat sich halbiert
Aber: Das Sieb von Eratosthenes bleibt schneller, weil es perfekt zur Hardware passt.
Es kombiniert:
einfache Operationen
lineare Speicherzugriffe
minimale Verzweigungen
Während Atkin mathematisch eleganter ist aber praktisch mehr Rechenaufwand pro Kandidat verursacht.
Hier geht‘ s zur Erklärung und Herleitung der Gleichungen
Python-Code
Die Ergebnisse lassen sich mit einer beliebigen lokalen oder webbasierten Python-Umgebung reproduzieren.
import math
import time
# ======================
# Classic XY-Atkin
# ======================
def atkin_classic(limit):
sieve = [False] * (limit + 1)
root = math.isqrt(limit) + 1
x1_max = math.isqrt(limit // 4)
x2_max = math.isqrt(limit // 3)
x3_max = math.isqrt(limit // 2)
valid_pairs = {
0: {1,2,3,4},
1: {0,2,3},
2: {0,1,4},
3: {0,1,4},
4: {0,2,3}
}
# ======================
# GL1 (mod5)
# ======================
y_starts_1 = [1,5,7,11,13,17,19,23,25,29]
y_starts_2 = [3,9,15,21,27]
# erste Gruppe
for x in range(1, x1_max + 1):
x2 = x*x
xm = x % 5
allowed = valid_pairs[xm]
for y0 in y_starts_1:
if (y0 % 5) not in allowed:
continue
y = y0
while y < root:
n = 4*x2 + y*y
if n > limit:
break
sieve[n] ^= True
y += 30
# zweite Gruppe
for x0 in (1,2):
for x in range(x0, x1_max + 1, 3):
x2 = x*x
xm = x % 5
allowed = valid_pairs[xm]
for y0 in y_starts_2:
if (y0 % 5) not in allowed:
continue
y = y0
while y < root:
n = 4*x2 + y*y
if n > limit:
break
sieve[n] ^= True
y += 30
# ======================
# GL2
# ======================
for x in range(1, x2_max + 1, 2):
x2 = x*x
y = 2
while y < root:
n = 3*x2 + y*y
if n > limit:
break
sieve[n] ^= True
yy = y + 2
n2 = 3*x2 + yy*yy
if n2 > limit:
break
sieve[n2] ^= True
y += 6
# ======================
# GL3 (y start)
# ======================
y_start_odd = 2
y_start_even = 1
for x in range(1, x3_max + 1, 2):
x2 = x*x
y = y_start_odd
while y < x:
n = 3*x2 - y*y
yy = y + 2
n2 = 3*x2 - yy*yy if yy < x else -1
if n <= limit or (n2 != -1 and n2 <= limit):
y_start_odd = y
break
y += 6
y = y_start_odd
while y < x:
n = 3*x2 - y*y
if 0 < n <= limit:
sieve[n] ^= True
yy = y + 2
if yy < x:
n2 = 3*x2 - yy*yy
if 0 < n2 <= limit:
sieve[n2] ^= True
y += 6
for x in range(2, x3_max + 1, 2):
x2 = x*x
y = y_start_even
while y < x:
n = 3*x2 - y*y
yy = y + 4
n2 = 3*x2 - yy*yy if yy < x else -1
if n <= limit or (n2 != -1 and n2 <= limit):
y_start_even = y
break
y += 6
y = y_start_even
while y < x:
n = 3*x2 - y*y
if 0 < n <= limit:
sieve[n] ^= True
yy = y + 4
if yy < x:
n2 = 3*x2 - yy*yy
if 0 < n2 <= limit:
sieve[n2] ^= True
y += 6
if limit >= 5:
sieve[5] = True
# Quadratschritt
for p in range(5, math.isqrt(limit) + 1):
if sieve[p]:
p2 = p*p
step = 6*p2
n1 = p2
n2 = 5*p2
while n1 <= limit or n2 <= limit:
if n1 <= limit:
sieve[n1] = False
n1 += step
if n2 <= limit:
sieve[n2] = False
n2 += step
return [2,3] + [n for n in range(5, limit+1) if sieve[n]]
# ======================
# Count-Version
# ======================
def atkin_count_xy_optimized(limit):
count = [0] * (limit + 1)
root = math.isqrt(limit) + 1
x1_max = math.isqrt(limit // 4)
x2_max = math.isqrt(limit // 3)
x3_max = math.isqrt(limit // 2)
valid_pairs = {
0: {1,2,3,4},
1: {0,2,3},
2: {0,1,4},
3: {0,1,4},
4: {0,2,3}
}
def add(n, x, y):
if n <= 0 or n > limit:
return
if count[n] == 2:
return
if count[n] == 0:
count[n] = 1 if math.gcd(x, y) == 1 else 2
elif count[n] == 1:
count[n] = 2
# ======================
# GL1 (mod5)
# ======================
y_starts_1 = [1,5,7,11,13,17,19,23,25,29]
y_starts_2 = [3,9,15,21,27]
# erste Gruppe
for x in range(0, x1_max + 1): # wichtig: x = 0 bleibt!
x2 = x*x
xm = x % 5
allowed = valid_pairs[xm]
for y0 in y_starts_1:
if (y0 % 5) not in allowed:
continue
y = y0
while True:
n = 4*x2 + y*y
if n > limit:
break
add(n, x, y)
y += 30
# zweite Gruppe
for x0 in (1,2):
for x in range(x0, x1_max + 1, 3):
x2 = x*x
xm = x % 5
allowed = valid_pairs[xm]
for y0 in y_starts_2:
if (y0 % 5) not in allowed:
continue
y = y0
while True:
n = 4*x2 + y*y
if n > limit:
break
add(n, x, y)
y += 30
# ======================
# GL2
# ======================
for x in range(1, x2_max + 1, 2):
x2 = x*x
y = 2
while True:
n = 3*x2 + y*y
if n > limit:
break
add(n, x, y)
yy = y + 2
n2 = 3*x2 + yy*yy
if n2 > limit:
break
add(n2, x, yy)
y += 6
# ======================
# GL3 (y start)
# ======================
y_start_odd = 2
y_start_even = 1
for x in range(1, x3_max + 1, 2):
x2 = x*x
y = y_start_odd
while y < x:
n = 3*x2 - y*y
yy = y + 2
n2 = 3*x2 - yy*yy if yy < x else -1
if n <= limit or (n2 != -1 and n2 <= limit):
y_start_odd = y
break
y += 6
y = y_start_odd
while y < x:
n = 3*x2 - y*y
if 0 < n <= limit:
add(n, x, y)
yy = y + 2
if yy < x:
n2 = 3*x2 - yy*yy
if 0 < n2 <= limit:
add(n2, x, yy)
y += 6
for x in range(2, x3_max + 1, 2):
x2 = x*x
y = y_start_even
while y < x:
n = 3*x2 - y*y
yy = y + 4
n2 = 3*x2 - yy*yy if yy < x else -1
if n <= limit or (n2 != -1 and n2 <= limit):
y_start_even = y
break
y += 6
y = y_start_even
while y < x:
n = 3*x2 - y*y
if 0 < n <= limit:
add(n, x, y)
yy = y + 4
if yy < x:
n2 = 3*x2 - yy*yy
if 0 < n2 <= limit:
add(n2, x, yy)
y += 6
if limit >= 5:
count[5] = 1
return [2,3] + [n for n in range(5, limit+1) if count[n] == 1]
# ======================
# Atkin Mod 60
# ======================
def atkin_mod60(limit):
sieve = [False] * (limit + 1)
root = math.isqrt(limit) + 1
x1_max = math.isqrt(limit // 4)
x2_max = math.isqrt(limit // 3)
x3_max = math.isqrt(limit // 2)
for x in range(1, x1_max + 1):
x2 = x*x
y = 1
while y < root:
n = 4*x2 + y*y
if n > limit:
break
if n % 60 in (1,13,17,29,37,41,49,53):
sieve[n] ^= True
y += 1
for x in range(1, x2_max + 1):
x2 = x*x
y = 1
while y < root:
n = 3*x2 + y*y
if n > limit:
break
if n % 60 in (7,19,31,43):
sieve[n] ^= True
y += 1
for x in range(1, x3_max + 1):
x2 = x*x
for y in range(1, x):
n = 3*x2 - y*y
if 0 < n <= limit and n % 60 in (11,23,47,59):
sieve[n] ^= True
for p in range(5, math.isqrt(limit) + 1):
if sieve[p]:
p2 = p*p
step = 6*p2
n1 = p2
n2 = 5*p2
while n1 <= limit or n2 <= limit:
if n1 <= limit:
sieve[n1] = False
n1 += step
if n2 <= limit:
sieve[n2] = False
n2 += step
return [2,3,5] + [i for i in range(6, limit+1) if sieve[i]]
# ======================
# Eratosthenes
# ======================
def eratosthenes(limit):
sieve = [True] * (limit + 1)
sieve[0] = sieve[1] = False
for p in range(2, math.isqrt(limit) + 1):
if sieve[p]:
sieve[p*p : limit+1 : p] = [False] * ((limit - p*p)//p + 1)
return [i for i in range(2, limit+1) if sieve[i]]
# ======================
# Benchmark
# ======================
if __name__ == "__main__":
limits = [100_000, 200_000, 500_000, 1_000_000]
print(f"{'Limit':>10} | {'XY-Atkin':>10} | {'Count-XY':>10} | {'Mod60':>10} | {'Eratosth.':>10} | {'OK':>3}")
print("-"*75)
for L in limits:
t0 = time.perf_counter()
p1 = atkin_classic(L)
t1 = time.perf_counter()
t2 = time.perf_counter()
p2 = atkin_count_xy_optimized(L)
t3 = time.perf_counter()
t4 = time.perf_counter()
p3 = atkin_mod60(L)
t5 = time.perf_counter()
t6 = time.perf_counter()
p4 = eratosthenes(L)
t7 = time.perf_counter()
ok = (set(p1) == set(p2) == set(p3) == set(p4))
print(f"{L:>10} | {t1-t0:>10.3f} | {t3-t2:>10.3f} | {t5-t4:>10.3f} | {t7-t6:>10.3f} | {'✓' if ok else '✗'}")