Come spiegare questo metodo per trovare il minimo comune multiplo dei primi n numeri naturali?

-2

Questa è la domanda n. 5 di Project Euler. L'affermazione è praticamente trovare il minimo comune multiplo dei primi n numeri naturali. Ad esempio, il minimo comune multiplo di 1, 2 .. 10 è 2520.

Ammetto che stavo solo provando cose a caso e non mi aspettavo che funzionasse (scritto in Python):

factors = int(input())
factorList = []

for i in range(2, factors+1):
    factorList.append(i)

for i in range(len(factorList)-1):
    for j in range(2*i+2, len(factorList), i+2):
            factorList[j] //= factorList[i]

result = 1
for i in range(len(factorList)):
    result *= factorList[i]

print (result)

Questo programma prende l'input, ad esempio 10. Quindi farà una lista dei numeri 2, 3 .. 10. Dopo, itererà ogni elemento, quindi lo dividerà dagli elementi procedurali ad intervalli del valore dell'elemento .

Ad esempio, inizierà a 2, che trasformerà l'array in 2, 3, 2, 5, 3, 7, 4, 9, 5 perché 4, 6, 8, 10 sono stati divisi per 2. Sarà fai lo stesso con 3, poi ancora 2 (4 diventano 2) fino a quando non termina il penultimo elemento. Quando questo viene eseguito in esecuzione sull'input 10, l'elenco appare come 2 3 2 5 1 7 2 3 1, che quindi moltiplicherò per ottenere la risposta.

Questo ha superato tutti i casi di test, ma non ho idea del perché funzioni. Davvero non mi aspettavo che funzionasse. Capisco che in qualche modo la lista finale contiene il numero massimo di ogni fattore primo da un singolo numero (ad esempio il mio esempio ha 2 * 2 * 2 da 8 e 3 * 3 da 9), ma non capisco come sia arrivato. Le altre soluzioni che ho trovato a questa domanda sono tutte più intuitive, usando la formula n! / (Gcd (1..n)) e la proprietà che gcd (a, b, c) = gcd (gcd (a, b ), c).

Se qualcuno potesse spiegare perché questo metodo è valido, lo apprezzerei.

    
posta Yifan 22.09.2016 - 08:54
fonte

1 risposta

1

Il tuo programma esegue in realtà il classico algoritmo Individuazione dei multipli comuni per fattore di costo .

La sequenza di divisioni rimuove da ciascun numero tutti i fattori primi più in basso nella matrice. L'array finisce con solo i fattori primi nel numero richiesto, quindi l'intero prodotto dà la risposta giusta.

    
risposta data 22.09.2016 - 18:46
fonte

Leggi altre domande sui tag