Jelenlegi hely

Legnagyobb közös osztó

Két szám legnagyobb közös osztója az a legnagyobb pozitív egész szám ami mind a két számnak osztója.

do
            {
                maradek=a%b;
            
                a=b;
                b=maradek;
            }
while(maradek!=0);
            
Console.WriteLine("A legnagyobb közös osztójuk: "+a);

Az algoritmus feltételezi, hogy a>=b. És érdemes vizsgálni, hogy b nem 0-e.

Euklidész algoritmusát használja, mely szerint:

(a,b)=(b,r) ahol         r --> a=n*b+r     és        a,b,r,n egész számok

Mit csinál az algoritmus:
A nagyobb számot elosztja a kisebbel. A keletkezett maradékot használja a következő lépésben, ahol már az előbbi kisebb számot osztja az előbb kapott maradékkal. Addig folytatja ameddig keletkezik az osztásnál maradék. Ha nem keletkezik már maradék, akkor az utoljára előállt maradék lesz a legnagyobb közös osztó. 

Theme by Danetsoft and Danang Probo Sayekti inspired by Maksimer