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.