Massimo comun divisore

Il massimo comun divisore di un elenco di interi è il più grande intero positivo che divide ogni valore elencato senza resto. Gli allievi incontrano questa idea come MCD o GCF nel senso numerico elementare, poi di nuovo quando semplificano rapporti, riducono frazioni ed estraggono un fattore comune da un insieme di misure. Questo calcolatore del massimo comun divisore accetta un elenco di numeri interi, prende il valore assoluto di ciascun termine così un segno meno non cambia mai la risposta, e riduce l'elenco con l'algoritmo di Euclide finché resta un unico fattore positivo.

Che cosa è il massimo comun divisore e come lo trova la riduzione euclidea

Il massimo comun divisore di due o più interi è il più grande intero positivo che divide ogni valore elencato senza resto. I corsi scolastici lo chiamano MCD, GCF o HCF; la teoria dei numeri chiama lo stesso oggetto massimo comun divisore. I segni non cambiano il fattore: dodici e meno diciotto condividono il fattore sei, perché la divisibilità si definisce sui valori assoluti.

Lo zero è divisibile per ogni intero, quindi l'MCD di zero e dodici è dodici, ma un elenco che contiene solo zeri non ha fattore comune positivo e viene rifiutato. L'algoritmo di Euclide calcola l'MCD binario senza elencare i fattori primi. Per una coppia a e b sostituisce a con b e b con a modulo b finché il resto è zero; l'ultimo resto non nullo è gcd(a, b).

L'associatività consente di piegare lo stesso passo su un elenco: gcd(a, b, c) è uguale a gcd(gcd(a, b), c). Esempio: dodici, diciotto e ventiquattro. gcd(12, 18) è sei perché 18 è uguale a 1 volte 12 più 6 e 12 è uguale a 2 volte 6 più 0; poi gcd(6, 24) è sei. La capacità restituisce quel sei positivo, mai un fattore negativo né un prodotto imbottito delle voci.

La fattorizzazione in primi darebbe la stessa risposta ma è più lenta per grandi magnitudini e più facile da sbagliare omettendo un primo condiviso; la riduzione euclidea usa solo resti ed è esatta su ogni intero sicuro del contratto. Un solo intero è ammesso: l'MCD di un valore è il suo valore assoluto, il che coincide con la definizione secondo cui ogni intero divide se stesso.

Contratto di ingresso, forma della risposta ed errori

Se una voce non è un intero, il gestore rifiuta la richiesta con un messaggio chiaro che il valore deve essere un intero; tali fallimenti non vengono fatturati. Un elenco di zeri è rifiutato perché zero non è un fattore positivo; mescolare zero con un intero non nullo è valido e restituisce l'MCD dei termini non nulli.

In caso di successo il corpo restituisce numbers, gli interi analizzati nell'ordine di ingresso con i segni originali; count, la lunghezza di quell'elenco; gcf, il massimo comun divisore positivo; e formula, la stringa gcf uguale a gcd dei valori assoluti tramite l'algoritmo di Euclide. Esempio: dodici, diciotto e ventiquattro producono gcf sei. Esempio: meno quarantotto, diciotto e trenta producono anch'essi gcf sei.

Dove il massimo comun divisore è utile

Le aule e le piattaforme di tutoraggio usano un calcolatore del massimo comun divisore così gli allievi verificano il passo di riduzione euclidea senza elencare i primi a mano né dimenticare che un segno meno non cambia il fattore. I generatori di esami necessitano di un oracolo deterministico che segni un elenco vuoto o un decimale come 12.5 come ingresso non valido invece di troncare in silenzio e restituire un MCD plausibile ma errato. La convalida fallita non consuma saldo.

Tenga le richieste entro il tetto di quaranta interi, fissi il gcf intero nei test, e Lei ottiene fattori comuni riproducibili per i compiti, i plugin LMS e i worker in periferia senza erigere un'infrastruttura simbolica propria.