Warum ist das eine falsche Implementierung von Fermat's Factorization?

Ich arbeite gerade durch Projekt Euler, und das war mein Versuch (in Python) bei Problem 3. Ich lief dies und ließ es für etwa 30 Minuten. Danach habe ich mir die Zahlen unter "Summe" angesehen. Ich fand mehrere Probleme: einige dieser Zahlen waren gerade, und daher nicht prim, und einige dieser Zahlen waren nicht einmal richtige Faktoren von n. Zugegeben, sie waren nur um 0,000001 aus (normalerweise ergab die Division x99999230984 oder was auch immer). Die Nummer, bei der ich schließlich aufhörte, war 3145819243.0.Warum ist das eine falsche Implementierung von Fermat's Factorization?

Kann jemand erklären, warum diese Fehler auftreten?

EDIT: Meine Interpretation des Theorems war im Grunde, dass, mit der Neuanordnung von Variablen, könnten Sie für x mit der Quadratwurzel von n + y^2 lösen, und y wäre brachial, bis es eine ganze Zahl war. Danach wäre der tatsächliche Primfaktor x + y.

Hier ist mein Code.

import math 
n = int(600851475143) 
y = int(1) 
while y >= 1: 
    if math.sqrt(n + (y**2)).is_integer(): 
     x = math.sqrt(n + (y**2)) 
     print "x" 
     print x 
     print "sum" 
     print x + y 
     if x + y > (600851475142/2): 
      print "dead" 
     else: 
      print "nvm" 
    y = y + 1

Quelle

2017-05-06 Liam Wilson

Ich gebe Ihnen einen Hinweis: [Sieve Algorithmus] (https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) Dies wird Ihr Leben mit dieser Herausforderung von Projecteuler und vielen anderen dort retten. Wenn Sie es schwierig finden, kann ich meine Antwort auf diese Frage mit 'Sieve-Algorithmus' posten. Andernfalls versuchen Sie es mit sich selbst, das ist die beste Vorgehensweise. Bedenken Sie auch eine Sache: Projecteulers Frage muss innerhalb von weniger als einer Minute gelöst werden. Wenn nicht, müssen Sie Ihren Ansatz/Algorithmus/Ihre Denkweise ändern. –

@ChihebNexus das Sieb ist gut, aber zu verstehen, warum diese Implementierung eines anderen Ansatzes nicht funktioniert, ist noch besser. Es gibt auch keine zeitliche Begrenzung für die Probleme von Euler. Wenn man einen Brute-Force-Ansatz verwenden möchte, warum nicht? – njzk2

@ njzk2 Ja, Sie haben einen Punkt hier. –

Typisches Problem mit großer Anzahl und Gleitkommapräzision.

Wenn Sie zu y = 323734167 gelangen, berechnen Sie , was math.sqrt(104804411734659032) ist.

Dies ist 3.23735095000000010811308548429078847808587868214170702... × 10^8 nach Wolfram alpha, d. H. Keine ganze Zahl, aber 323735095.0 nach Python.

Wie Sie sehen können, hat Python nicht die Genauigkeit, um die .00000001... zu sehen.

Statt Test is_integer, können Sie das Quadrat des Ergebnisses testen:

> 323735095 ** 2 
=> 104804411734659025

und sehen, ob es die Eingabe übereinstimmt (es nicht, die Eingabe 104804411734659032, off von 7).

Quelle

2017-05-06 02:09:33 njzk2

Oh ok. Ansonsten ist die Implementierung korrekt? –

gibt es Raum für Optimierung, aber es sieht wie eine gültige Implementierung der Fermat-Faktorisierung aus. Sie müssen jedoch eine bessere Quadratwurzel finden. – njzk2

(siehe http://stackoverflow.com/questions/30490439/how-to-take-square-root-of-large-numbers-in-python) – njzk2

Warum ist das eine falsche Implementierung von Fermat's Factorization?

Antwort

Verwandte Themen