Problemi con i numeri primi

StackOverflow https://stackoverflow.com/questions/1877255

  •  18-09-2019
  •  | 
  •  

Domanda

Sto cercando di scrivere un programma per trovare il più grande fattore primo di un numero molto grande, e ho provato diversi metodi con successo variabile. Tutti quelli che ho trovato finora sono stati incredibilmente lento. Ho avuto un pensiero, e mi chiedo se questo è un valido approccio: 

long number = input;

while(notPrime(number))
{
    number = number / getLowestDivisiblePrimeNumber();
}

return number;

Questo approccio avrebbe preso un input, e farebbe il seguente:

200 -> 100 -> 50 -> 25 -> 5 (ritorno)

90 -> 45 -> 15 -> 5 (ritorno)

Si divide currentNum ripetutamente il più piccolo numero divisibile (più spesso 2 o 3) fino a currentNum sé è primo (non v'è alcun numero primo divisibile inferiore alla radice quadrata di currentNum), e assume questo è il più grande fattore primo della ingresso originale.

Sarà questo lavoro sempre? In caso contrario, qualcuno può darmi un controesempio?

-

EDIT:. Con molto grande, voglio dire circa 2 ^ 40, o 10 ^ 11

È stato utile?

Soluzione

Questo funziona sempre a causa della unico Primo fattorizzazione Teorema .

Altri suggerimenti

Il metodo funzionerà, ma sarà lenta. "Quanto sono grandi i numeri?" determina il metodo da utilizzare:

Certo che funzionerà (vedi Mark Byers' risposta ), ma per gli ingressi "molto grandi" potrebbe richiedere troppo tempo. Si dovrebbe notare che la chiamata a getLowestDivisiblePrimeNumber() nasconde un altro loop, quindi questo funziona a O (N ^ 2), e che a seconda di ciò che si intende per "molto grande" che può avere per lavorare su bignum che sarà lenta.

Si potrebbe accelerarlo un po ', notando che l'algoritmo non deve mai controllare i fattori più piccoli di quello precedente quello trovato.

Si sta tentando di trovare le href="http://en.wikipedia.org/wiki/Prime_factor" di un numero. Quello che si sta proponendo lavoro sarà, ma sarà comunque lento per grandi numeri .... si dovrebbe essere grati per questo, poiché la maggior parte di sicurezza moderna si basa su questo essere un problema difficile.

Da una rapida ricerca ho appena fatto, il modo più veloce conosciuto per fattorizzare un numero è quello di utilizzare il metodo di curva ellittica.

Si potrebbe provare a lanciare il proprio numero in questa demo: http://www.alpertron.com .AR / ECM.HTM .

Se si convince che, si potrebbe provare a rubare sia il codice (che non è divertente, che forniscono un collegamento ad esso!) O la lettura sulla teoria della altrove. C'è un articolo di Wikipedia su di esso qui: http://en.wikipedia.org/wiki/Lenstra_elliptic_curve_factorization ma io sono troppo stupido per capirlo. Per fortuna, è il tuo problema, non mio! :)

La cosa con Project Euler è che di solito c'è un metodo evidente forza bruta per fare il problema, che avrà quasi sempre. Mentre le domande diventano più difficili, è necessario implementare soluzioni intelligenti.

Un modo per risolvere questo problema è quello di utilizzare un ciclo che trova sempre il più piccolo (intero positivo) fattore di un numero. Quando il fattore più piccolo di un numero è quel numero, allora avete trovato il più grande fattore primo!

Descrizione dettagliata Algoritmo:

È possibile farlo mantenendo tre variabili:

Il numero che si sta tentando di fattore (A) Un negozio divisore corrente (B) Un grande negozio divisore (C)

Inizialmente, lasciare che (a) è il numero che ti interessa - in questo caso, è 600851475143. Allora (B) essere 2. Avere un condizionale che controlla se (A) è divisibile per (B). Se è scindibile, divide (A) (B), reset (B) a 2, e tornare a verificare se (A) è divisibile per (B). Altrimenti, se (A) non è divisibile per (B), incremento (B) di +1 e poi verificare se (A) è divisibile per (B). Eseguire il ciclo finché (a) è 1. L'(3) si ritorna sarà il più grande divisore primo di 600.851.475.143.

Ci sono molti modi si potrebbe fare questo più efficace - invece di incrementare al successivo numero intero, si potrebbe avanzare fino al successivo numero intero necessariamente privilegiata, e invece di mantenere un grande negozio divisore, si può solo tornare il numero corrente quando il suo solo divisore è stessa. Tuttavia, l'algoritmo che ho descritto sopra verrà eseguito in pochi secondi a prescindere.

L'implementazione in Python è il seguente: - 

def lpf(x):
        lpf = 2;
        while (x > lpf):
                if (x%lpf==0):
                        x = x/lpf
                        lpf = 2
                else:
                        lpf+=1;
        print("Largest Prime Factor: %d" % (lpf));

def main():
        x = long(raw_input("Input long int:"))
        lpf(x);
        return 0;

if __name__ == '__main__':
    main()

Esempio: Troviamo il più grande fattore primo della 105 con il metodo sopra descritto

.

Sia (A) = 105. (B) = 2 (abbiamo sempre iniziare con 2), e non abbiamo un valore per (C) ancora.

è (a) divisibile per (B)? No. Incremento (B) 1: (B) = 3. Is Is (A) divisibile per (B)? Sì. (105/3 = 35). Il più grande divisore trovato finora è 3. Sia (C) = 3. Update (A) = 35. Reset (B) = 2.

Ora, è (A) divisibile per (B)? No. Incremento (B) 1: (B) = 3. è (a) divisibile per (B)? No. Incremento (B) 1: (B) = 4. è (a) divisibile per (B)? No. Incremento (B) 1: (B) = 5. è (A) divisibile per (B)? Sì. (35/5 = 7). Il più grande divisore abbiamo trovato in precedenza viene memorizzato in (C). (C) è attualmente 3. 5 è maggiore di 3, in modo da aggiornare (C) = 5. aggiornare (A) = 7. Abbiamo reset (B) = 2.

Poi si ripete il processo per la (A), ma ci sarà solo continuare incremento (B) fino a (B) = (A), perché 7 è primo e non ha divisori diversi da se stesso e 1. (Potremmo già smettere quando (B)> ((a) / 2), in quanto non si può avere divisori intero maggiore della metà di un numero - il divisore più piccolo possibile (diverso da 1) di qualsiasi numero è 2)

A quel punto torniamo (A) = 7.

Prova a fare alcuni di questi a mano, e si otterrà il blocco dell'idea

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top