Algoritmul lui Euclid

Aspecte teoretice:

În matematică, algoritmul lui Euclid este o metodă eficientă de calcul al celui mai mare divizor comun (CMMDC). El este denumit după matematicianul grec Euclid, care l-a descris în Cărțile VII și X din “Elementele”.

CMMDC al două numere este cel mai mare număr care le divide pe ambele. Algoritmul lui Euclid exploatează observația că cel mai mare divizor comun al două numere nu se modifică dacă numărul cel mai mic este scăzut din cel mai mare. De exemplu, 21 este CMMDC al numerelor 252 și 105 (252 = 21 × 12; 105 = 21 × 5); întrucât 252 − 105 = 147, CMMDC al lui 147 și 105 este tot 21. Cum cel mai mare dintre cele două numere este redus, repetarea acestui proces dă numere din ce în ce mai mici, până când unul dintre ele este 0. Când se întâmplă aceasta, CMMDC este celălalt număr, cel nenul. Inversând pașii algoritmului lui Euclid, CMMDC se poate exprima sub formă de suma celor două numere inițiale, fiecare înmulțite cu un întreg pozitiv sau negativ, de exemplu: 21 = 5 × 105 + (−2) × 252.

Implementare:

Cod Sursa C++

 

#include "stdafx.h"
#include<iostream>
 
using namespace std;
 
int a, b, r;
int main()
{
	cout << "dati primul numar = ";
	cin >> a;
	cout << "dati al doilea numar = ";
	cin >> b;
	while (b>0)
	{
		r = a%b;
		a = b;
		b = r;
	}
	cout <<"CMMDC pentru cele doua numere este: "<<a<<endl;
	system("pause");
}

Cod Sursa C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace EuclidCS
{
    class Program
    {
        static void Main(string[] args)
        {
            int a, b, r;
            Console.Write("Dati primul numar: ");
            a = Convert.ToInt32(Console.ReadLine());
            Console.Write("Dati al doilea numar: ");
            b = Convert.ToInt32(Console.ReadLine());
            while (b>0)
            {
                r = a % b;
                a = b;
                b = r;
            }
            Console.WriteLine("CMMDC pentru cele doua numere este: " + a);
            Console.ReadKey();
        }
    }
}

Cod Sursa VB

 

Module Module1
 
    Sub Main()
        Dim a As Integer, b As Integer, r As Integer
        Console.Write("Dati primul numar: ")
        a = Convert.ToInt32(Console.ReadLine())
        Console.Write("Dati al doilea numar: ")
        b = Convert.ToInt32(Console.ReadLine())
        While b > 0
            r = a Mod b
            a = b
            b = r
        End While
        Console.WriteLine("CMMDC pentru cele doua numere este: " & a)
        Console.ReadKey()
 
    End Sub
 
End Module

Rezultat: