Deutsch
Deutsch
In der Zahlentheorie ist der Lucas-Lehmer-Primzahltest eine effiziente Methode zur Bestimmung, ob eine Mersenne-Zahl eine Primzahl ist. In diesem Artikel kombinieren wir die PHP-Sprache und die GMP-Erweiterung (GNU Multiple Precision Arithmetic Library, GNU Multiple Precision Math Library), um den Lucas-Lehmer-Primalitätstest zu implementieren und ein vollständiges Codebeispiel bereitzustellen.
Der Lucas-Lehmer-Primalitätstest ist ein Algorithmus, der speziell entwickelt wurde, um zu erkennen, ob eine Mersenne-Zahl der Form M = 2^n - 1 eine Primzahl ist, wobei n eine positive ganze Zahl größer als 1 ist. Der Test basiert auf der Lucas-Lehmer-Folge. Es berechnet iterativ jedes Element der Folge und bestimmt schließlich, ob das letzte Element der Folge Null ist, wodurch die Primalität der Mersenne-Zahl bestimmt wird.
Die integrierten Funktionen von PHP können keine sehr großen Ganzzahloperationen verarbeiten, daher ist die GMP-Erweiterung erforderlich. Bei der Installation von PHP können Sie eine Version mit aktivierten GMP-Erweiterungen auswählen oder GMP-Erweiterungen in Ihrer vorhandenen Umgebung aktivieren.
Funktion lucasLehmerTest($n)
{
$s = '4';
$m = gmp_pow('2', $n) - '1';
for ($i = 1; $i < $n - 1; $i++) {
$s = gmp_mod(gmp_pow($s, 2) - 2, $m);
}
if ($s == '0') {
return true;
}
return false;
}Analyse:
In der Funktion wird gmp_pow verwendet, um 2 hoch $n$ minus 1 zu berechnen, um $m$ zu erhalten, dann $n-1$-mal zu iterieren, um die Lucas-Lehmer-Folge zu berechnen, und schließlich zu bestimmen, ob das letzte Element der Folge Null ist, um die Primalität zu bestimmen.
$exponenten = [2, 3, 5, 7, 13, 17];
foreach ($exponents als $exponent) {
$result = lucasLehmerTest($exponent);
if ($result) {
echo "2^$exponent - 1 ist eine Primzahl.";
} anders {
echo "2^$exponent - 1 ist keine Primzahl.";
}
}Analyse:
Wir definieren ein Array $exponents, das mehrere Exponentenwerte enthält, und rufen dann mithilfe einer foreach-Schleife die Lucas-Lehmer-Primalitätstestfunktion auf, um Beurteilungsinformationen basierend auf den Testergebnissen auszugeben.
Durch PHP- und GMP-Erweiterungen können Sie den Lucas-Lehmer-Primzahltest einfach implementieren und bestimmen, ob eine große ganze Zahl eine Primzahl ist. Für die Primzahlbeurteilung großer Mersenne-Zahlen ist der Lucas-Lehmer-Algorithmus effizienter und kann schneller Ergebnisse liefern. Die in diesem Artikel bereitgestellten Codebeispiele können als praktische Referenz verwendet werden.
