NWD - algorytm Euklidesa

Algorytm Euklidesa służy do wyznaczania największego wspólnego dzielnika dwóch liczb całkowitych. Największy wspólny dzielnik dwóch liczb a i b, to taka liczba, która dzieli te liczby bez reszty i jest ona możliwie największa. Można go zastosować do skracania ułamków lub wyznaczenia najmniejszej wspólnej wielokrotności NWW.
Sposób rozwiązania jest następujący.Wybieramy większą z dwóch liczb i zamieniamy ją na różnicę większej i mniejszej. Czynność tą powtarzamy do momentu uzyskania dwóch takich samych wartości.

Strona zawiera:

• Schemat blokowy
• Kod cpp
• Kod python
• Skrypt JS
• Działający skrypt JS

Schemat blokowy

Kod cpp

#include <iostream>
using namespace std;

int main()
{
    int a,b;
    cin >> a >> b;

    while(a != b)
        if(a > b) a -= b;
        else      b -= a;

    cout << a << endl;

    return 0;
}

Kod python

def NWD(a,b):
    while a != b:
        if a>b: a -= b
        else: b -= a
    return a
 
a = int(input())
b = int(input())
 
print(NWD(a,b))

Skrypt JS

<script>
	function f1()
	{
		var a = document.getElementById("a").value;
		var b = document.getElementById("b").value;
		var t;
		
		while(a != b)
		{
			if(a < b) b = b - a;
			else a = a - b;
		}
		
		t = a
		
		document.getElementById("wynik").innerHTML = t;	
	}

</script>