Schnelle Factoring-Algorithmen? [geschlossen]

8

Wie kann ich schnell alle Faktoren einer Nummer finden?

z. B .:

  

Ziffer: 20
  Faktoren: {1 * 20, 2 * 10, 4 * 5, 5 * 4, 10 * 2, 20 * 1}

    
fronthem 21.07.2011, 08:49
quelle

7 Antworten

4

Das ist eigentlich ein Problem, für das keine gute Lösung bekannt ist. Aus diesem Grund hängt die RSA-Verschlüsselung tatsächlich von der Rechenschwierigkeit der Faktorisierungszahlen ab. Siehe: Ganzzahl-Faktorisierung

Sie können jedoch möglicherweise die bereits angegebenen Algorithmen beschleunigen, indem Sie nur Zahlen bis zur Quadratwurzel von n betrachten und prüfen, ob es sich um Faktoren handelt, indem Sie überprüfen, ob n % i == 0 . Wenn dies der Fall ist, können Sie den entsprechenden Faktor größer als n^(.5) finden, indem Sie n / i übernehmen.

    
Patrick 21.07.2011 09:15
quelle
3

Wenn die Zahl, nach der Sie die Faktoren suchen möchten, ungerade ist, müssen Sie nur ungerade Zahlen testen, da es unmöglich ist, einen geraden Faktor für eine ungerade Zahl zu haben. Mit einer Pre-Check-Up-Front können Sie sich also etwas Verarbeitung ersparen.

%Vor%     
Devon 03.11.2011 22:38
quelle
2

Gehen Sie durch eine Schleife, die den Modul auf alle Zwischenzahlen anwendet.

%Vor%     
Edgar Velasquez Lim 21.07.2011 08:57
quelle
0

Wahrscheinlich möchten Sie sich für den Modulo-Operator (%) entscheiden.

ZB

%Vor%     
Javascript is GOD 21.07.2011 08:57
quelle
0
%Vor%     
Nico Huysamen 21.07.2011 09:02
quelle
0
%Vor%

}

%Vor%

}

die Eingabe
210
Ausgabe von
2 3 5 7

    
deepakl.2000 21.07.2011 09:06
quelle
0
%Vor%

Ausgabe:

%Vor%     
Eng.Fouad 21.07.2011 08:59
quelle

Tags und Links

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Wie erkenne ich die Tonfrequenz / Tonhöhe auf einem iPhone? [geschlossen]