Python. Finde den Faktor der großen Zahl.

Wie findet man den Faktor der Nummer wie 23021532394741645684048066898202337277441635046162952078575443342063780035504608628272942696526664263794691 in Python?Python. Finde den Faktor der großen Zahl.

Es sollte nicht prime sein. Jeder Faktor außer 1 und Nummer - akzeptabel.

Ich überprüfte Lösungen wie von here ohne Ergebnis.

Naive Lösung wie:

def factor(n): 
    i = 2 
    limit = n/2 
    while i <= limit: 
     if n % i == 0: 
     return i 
     i += 1 
    return 1

auch nicht funktionieren.

Quelle

2016-04-09 Nikolay Fominyh

Huh. Die verknüpfte Frage hat eine Antwort mit 103, und sie "funktioniert nicht"? Welchen Code laufen * Sie eigentlich, wenn Sie ihn testen, wie verhält sich der Testcode und welches Verhalten haben Sie erwartet? –

Antwort mit 103 wird mit Fehler 'long int zu groß, um in float zu konvertieren' fehlschlagen. Außerdem wird der Fehler "OverflowError: range() result hat zu viele Elemente" erfüllt. Meine Frage ist mehr über Algorithmus zum Finden eines Faktors sehr großer Zahl. –

Wenn Sie eine zuverlässige Möglichkeit finden, Zahlen dieser Größe zu faktorisieren, werden Sie berühmt und brechen viele Verschlüsselungssysteme aus. – interjay

Pollard's Rho ist ein gutes Werkzeug zum Faktorisieren großer Zahlen mit relativ kleinen Primfaktoren. Hier ist eine naive Umsetzung:

import random 
from fractions import gcd 

def pollardRho(n, seed = None): 
    def f(x): return (x**2 + 1) % n 
    if seed == None: seed = random.randint(0,n-1) 
    t = h = seed 
    t = f(t) 
    h = f(f(h)) 
    d = gcd(t-h,n) 
    while d == 1: 
     t = f(t) 
     h = f(f(h)) 
     d = gcd(t-h,n) 
    return d,n//d

Dies findet den 10-stellige Faktor der n in der Frage in ein paar Sekunden. Als Übung können Sie einige der im Wikipedia-Artikel beschriebenen Beschleunigungen implementieren. Damit fällt der 13-stellige Faktor in etwa einer Minute. Ich bin mir nicht sicher, ob ich die Geduld für den 25-stelligen Faktor habe, aber es sollte grenzwertig sein.

Quelle

2016-04-09 21:10:18

Python. Finde den Faktor der großen Zahl.

Antwort

Verwandte Themen