Algoritmo di Euclide
Per 1071 e 462 il massimo comun divisore è 21, raggiunto in tre divisioni: 1071 = 462 × 2 + 147, poi 462 = 147 × 3 + 21 e infine resto zero. Inserisca due interi e veda ogni passaggio, non solo il risultato. Gratis nel suo browser.
- Gratis
- Funziona nel suo browser
- Senza registrazione
- I suoi dati restano sul dispositivo
Esegui gratis nel browser
Esempio risolto
- A
- 1071
- B
- 462
- Gcd
- 21
- Numero di passaggi
- 3
Il calcolatore dell'algoritmo di Euclide prende due interi e calcola il loro massimo comune divisore come Euclide descrisse più di duemila anni fa: dividendo ripetutamente e conservando il resto. Invece di restituire solo il numero finale, restituisce l'elenco completo dei passaggi — ogni riga nella forma dividendo = divisore × quoziente + resto — così può vedere esattamente come è stata raggiunta la risposta. Accetta valori negativi (l'MCD usa i valori assoluti), rifiuta input non interi e respinge il caso indefinito mcd(0,0).
Cosa fa davvero l'algoritmo di Euclide
Il massimo comune divisore di due interi è il numero più grande che li divide entrambi senza lasciare resto. L'algoritmo di Euclide lo trova senza fattorizzare nulla, ed è per questo che resta veloce anche con input molto grandi. L'idea è semplice: se un numero divide sia a sia b, divide anche il resto della divisione di a per b.
Quindi si sostituisce la coppia (a, b) con (b, a mod b) e si ripete. Ogni passaggio è una divisione lunga — per esempio, 1071 = 462 × 2 + 147 — e si continua finché il resto non è zero. L'ultimo resto diverso da zero è l'MCD.
Poiché il resto si riduce strettamente a ogni passaggio, il ciclo termina sempre, e termina in fretta: il numero di passaggi è proporzionale al logaritmo dell'input minore.
Input, casi limite e come vengono segnalati gli errori
Invia due campi, a e b, ed entrambi devono essere interi. Gli interi negativi sono validi: l'MCD è definito sui valori assoluti, quindi mcd(-1071, 462) equivale a mcd(1071, 462), e l'elenco dei passaggi è calcolato sui valori assoluti. Lo zero è un input valido per uno dei campi — mcd(a, 0) è |a| e in quel caso l'elenco dei passaggi è vuoto perché non serve alcuna divisione —, ma entrambi i campi a zero vengono rifiutati, perché mcd(0,0) è matematicamente indefinito.
Gli errori non producono mai una risposta parziale: la richiesta viene rifiutata con un codice leggibile dalla macchina e un messaggio che può mostrare all'utente.
Dove un MCD passo dopo passo si rivela utile
L'MCD puro è una commodity: ogni linguaggio ne ha uno nella libreria standard. Ciò che questa capacità aggiunge è la traccia. Insegnanti e studenti usano l'elenco dei passaggi per verificare che un esercizio sia stato risolto con il vero algoritmo di Euclide e non indovinando i divisori.
Gli sviluppatori lo usano per il debug della semplificazione di frazioni, della riduzione dei rapporti d'aspetto o dei controlli di coprimalità, perché vedere 252 = 105 × 2 + 42 indica esattamente dove un calcolo manuale diverge dal codice. Chi studia crittografia incontra l'algoritmo come fondamento della versione estesa che produce i coefficienti di Bézout e gli inversi modulari; vedere prima i semplici passaggi di divisione rende quel salto molto più facile.
Casi d'uso
Correggere un esercizio svolto
Incolla i due numeri di un compito e confronta i Suoi passaggi di divisione scritti con quelli che l'algoritmo produce davvero.
Semplificare frazioni e rapporti
Ottenga l'MCD di un numeratore e di un denominatore per ridurre una frazione, con l'elenco dei passaggi come traccia di audit di come è stato trovato il divisore.
Insegnare l'algoritmo prima della versione estesa
Mostri prima agli studenti la semplice traccia delle divisioni, poi passi ai coefficienti di Bézout e agli inversi modulari costruiti sullo stesso ciclo.
Domande frequenti
Quanto costa?
L'esecuzione è gratuita anche nel Suo browser su questa pagina.
Perché mcd(0,0) viene rifiutato?
Perché il massimo comune divisore di zero e zero è indefinito: ogni intero divide zero, quindi non ce n'è uno che sia il maggiore. Fornisca almeno un valore diverso da zero.
Posso passare numeri negativi?
Sì. L'MCD è calcolato sui valori assoluti, quindi mcd(-1071, 462) restituisce lo stesso risultato di mcd(1071, 462).
Cosa contiene l'array steps?
Un oggetto per divisione: dividendo, divisore, quoziente e resto, così ogni riga si legge dividendo = divisore × quoziente + resto. L'ultimo resto diverso da zero è l'MCD.
Quanto grandi possono essere gli input?
Fino all'intero sicuro massimo, 9007199254740991, così ogni quoziente e ogni resto dell'output è esatto.
Strumenti correlati
Per sviluppatori — accesso via API
Tutto quello che vedi in questa pagina è disponibile anche via API. Questa sezione è per i team che vogliono integrarlo nei propri sistemi; chi non ne ha bisogno può semplicemente usare lo strumento qui sopra.
Endpoint
Autenticazione con Bearer token: un POST mette in coda l'attività e il risultato arriva via webhook o link firmato.
Chiamala dal tuo stack
curl -X POST https://api.kit.forhosting.com/math/euclidean-algorithm \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"a":1071,"b":462}'const res = await fetch("https://api.kit.forhosting.com/math/euclidean-algorithm", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"a": 1071,
"b": 462
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/math/euclidean-algorithm",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"a": 1071,
"b": 462
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/math/euclidean-algorithm", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"a":1071,"b":462}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"a":1071,"b":462}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/math/euclidean-algorithm", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)Esempio di richiesta
{
"a": 1071,
"b": 462
}Esempio di risposta
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "math.euclidean_algorithm",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}L'API è asincrona: ricevi subito un task_id e puoi fare polling fino a 1 richiesta al secondo.
Prezzi
Prezzo pubblicato, senza token né crediti. Se l'attività fallisce, non paghi.
Limiti
max_abs | 9007199254740991 |
Errori
| HTTP | Codice | Significato |
|---|---|---|
401 | unauthorized | Chiave API mancante o non valida: controlla l'header Authorization. |
402 | insufficient_balance | Credito esaurito: ricarica per continuare a eseguire attività. |
404 | unknown_type | Tipo di attività sconosciuto: controlla il campo type della richiesta. |
429 | rate_limited | Troppe richieste in poco tempo: rallenta e riprova tra qualche secondo. |
Note tecniche
Lo stesso codice viene eseguito gratis nel Suo browser su questa pagina e tramite l'API a pagamento.
Cosa fa davvero l'algoritmo di Euclide
Questo endpoint esegue esattamente quella procedura e Le restituisce ogni divisione effettuata, non solo la conclusione, il che lo rende utile sia per correggere i compiti sia per verificare un calcolo all'interno di un sistema più grande.
Input, casi limite e come vengono segnalati gli errori
Le stringhe numeriche che rappresentano interi esatti, come "1071", sono accettate; decimali, frazioni, notazione scientifica e valori non numerici vengono rifiutati con un errore invalid_input che spiega cosa non ha funzionato. I valori sono limitati dall'intervallo degli interi sicuri dei double IEEE 754, circa 9 biliardi, quindi ogni quoziente e ogni resto dell'output è esatto.
Domande tecniche
Cosa conta come intero?
Un numero JSON senza parte frazionaria, oppure una stringa di cifre con segno iniziale facoltativo. Decimali, notazione scientifica e valori non numerici vengono rifiutati con un errore invalid_input.