Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- profil:klasse9:abschnitt-9-1-1-loe1-2 [2021/09/10 07:28] – lutz
+++ profil:klasse9:abschnitt-9-1-1-loe1-2 [2021/09/10 08:45] (aktuell) – lutz
@@ Zeile 34: / Zeile 34: @@
         if istPrimzahl(a):
             if istPrimzahl(b):
+                break
+        a += 1
+        b -= 1
+    print(a,"+",b,"=",n)
+    t = input("Nochmal? J/N: ")
+</code>
+<code python goldbach_miller_rabin.py>
+import random
+def istPrimzahl(n,k):
+    # Implementation uses the Miller-Rabin Primality Test
+    # The optimal number of rounds for this test is 40
+    # See http://stackoverflow.com/questions/6325576/how-many-iterations-of-rabin-miller-should-i-use-for-cryptographic-safe-primes
+    # for justification
+    # If number is even, it's a composite number
+    if n < 0:
+        return False
+    if n == 1:
+        return False
+    if n == 2 or n == 3:
+        return True
+    if n % 2 == 0:
+        return False
+    r, s = 0, n - 1
+    while s % 2 == 0:
+        r += 1
+        s //= 2
+    for _ in range(k):
+        a = random.randrange(2, n - 1)
+        x = pow(a, s, n)
+        if x == 1 or x == n - 1:
+            continue
+        for _ in range(r - 1):
+            x = pow(x, 2, n)
+            if x == n - 1:
+                break
+        else:
+            return False
+    return True
+t = "J"
+while t == "J":
+    n = int(input("Gerade Zahl größer 2: "))
+    while not(n > 2 and n%2 == 0):
+        n = int(input("Gerade Zahl größer 2: "))
+    a = 2
+    b = n-2
+    while a <= n//2:
+        if istPrimzahl(a,1):
+            if istPrimzahl(b,1):
                 break
         a += 1