PHP & Python: Algorithmen für Quersumme, Primfaktorzerlegung & Primzahlen

In diesem Blogbeitrag möchte ich gemeinsam mit dir darüber sprechen, wie man effiziente Algorithmen für einige mathematische Probleme wie Quersumme, Primfaktorzerlegung und Primzahlen in PHP und Python implementieren kann.

Quersumme

Beginnen wir mit der Quersumme. Die Quersumme einer Zahl ist die Summe der einzelnen Ziffern. Zum Beispiel ist die Quersumme von 1234 gleich 10, da 1+2+3+4=10. In PHP kann man die Quersumme einer Zahl wie folgt berechnen:

function quersumme($n) {
   $sum = 0;
   while($n != 0) {
      $sum += $n % 10;
      $n = $n / 10;
   }
   return $sum;
}

Dieser Algorithmus verwendet eine While-Schleife, um die Ziffern von $n nacheinander zu extrahieren und zur Gesamtsumme hinzuzufügen. In Python sieht der Algorithmus ähnlich aus:

def quersumme(n):
   sum = 0
   while n != 0:
      sum += n % 10
      n = n // 10
   return sum

Der einzige Unterschied hier ist, dass man den Operator // verwendet, um eine ganzzahlige Division durchzuführen.

Primfaktorzerlegung

Als nächstes wollen wir die Primfaktorzerlegung betrachten. Die Primfaktorzerlegung einer Zahl ist die Darstellung dieser Zahl als Produkt von Primzahlen. Zum Beispiel ist die Primfaktorzerlegung von 12 gleich 2•2•3. In PHP kann man die Primfaktorzerlegung wie folgt implementieren:

function primfaktorzerlegung($n) {
   $result = array();
   for($i = 2; $i <= $n; $i++) {
      while($n % $i == 0) {
         $result[] = $i;
         $n /= $i;
      }
   }
   return $result;
}

Dieser Algorithmus verwendet eine For-Schleife, um die Primzahlen von 2 bis $n nacheinander zu überprüfen. Wenn eine Primzahl ein Teiler von $n ist, wird sie zur Liste der Primfaktoren hinzugefügt, und $n wird durch diese Primzahl dividiert. Der Algorithmus läuft weiter, bis $n keine Primfaktoren mehr hat. In Python sieht der Algorithmus ähnlich aus:

def primfaktorzerlegung(n):
   result = []
   i = 2
   while i <= n:
      if n % i == 0:
         result.append(i)
         n //= i
      else:
         i += 1
   return result

Dieser Algorithmus verwendet eine While-Schleife und eine ähnliche Logik wie die PHP-Implementierung.

Primzahlprüfung

Schließlich wollen wir uns mit der Primzahlprüfung befassen. Eine Primzahl ist eine natürliche Zahl, die größer als 1 ist und nur durch 1 und sich selbst teilbar ist. Beispiele für Primzahlen sind 2, 3, 5, 7, 11, 13, 17 usw. Die Primzahlprüfung ist ein wichtiger Bestandteil vieler kryptografischer Verfahren und spielt auch in der Mathematik eine wichtige Rolle.

Naiver Ansatz zur Primzahlprüfung

Der einfachste Ansatz zur Prüfung, ob eine Zahl eine Primzahl ist, ist der sogenannte «naive» Ansatz. Dabei wird einfach überprüft, ob die Zahl durch eine andere Zahl als 1 und sich selbst teilbar ist. Hier ein Beispielcode in PHP:

function is_prime($num) {
    for ($i = 2; $i < $num; $i++) {
        if ($num % $i == 0) {
            return false;
        }
    }
    return true;
}

Dieser Ansatz ist jedoch sehr ineffizient für große Zahlen, da er für jede Zahl bis zur Wurzel der zu prüfenden Zahl eine Modulo-Operation durchführen muss.

Effizientere Algorithmen

Es gibt mehrere effizientere Algorithmen zur Primzahlprüfung. Einer der bekanntesten ist der Sieb des Eratosthenes, der alle Primzahlen bis zu einer bestimmten Grenze berechnet. Hier ein Beispielcode in Python:

def primes_sieve(limit):
    primes = [True] * limit
    primes[0] = primes[1] = False
    for i in range(2, int(limit ** 0.5) + 1):
        if primes[i]:
            primes[i*i: limit: i] = [False] * len(primes[i*i: limit: i])
    return [i for i in range(limit) if primes[i]]

Dieser Algorithmus ist wesentlich schneller als der naive Ansatz und eignet sich auch für große Zahlen.

Ein weiterer effizienter Algorithmus ist der Miller-Rabin-Test, der eine Zahl mit hoher Wahrscheinlichkeit als Primzahl identifiziert.

---

Ich würde mich sehr freuen, wenn du deine Gedanken und Erfahrungen zu diesem Thema mit mir teilst. Hast du weitere Tipps oder Tricks, um effiziente Algorithmen für die Prüfung von Primzahlen in PHP oder Python zu implementieren? Oder möchtest du einfach nur deine Meinung zu diesem Thema teilen? Schreibe gerne einen Kommentar und lasse es mich wissen!