Kłopot z algorytmem Euklidesa

suriel_k · Post autor: **suriel_k** » 4 paź 2006, o 19:26

próbuję obliczać NWD dla liczb np 2005 i 652 i wychodzi 1 wg algorytmu euklidesa.
Ale korzystając z tego samego algorytmu dla liczb np 6 i 12 nie wychodzi mi. a powinien być 6 ? gdzie znaleźć jakąś podpowiedź ?

Edited by Rogal: temacik poprawiłem, zapoznaj się z linkiem na ten temat w moim podpisie.

Rogal · Post autor: **Rogal** » 4 paź 2006, o 19:45

Eeekhm, jeśli zastosujemy algorytm Euklidesa dla liczb 12 i 6 to mamy:
12 : 6 = 2 r 0, więc NWD = 6
Jeśli weźmiemy 14 i 8 to będziemy mieć:
14 : 8 = 1 r 6
8 : 6 = 1 r 2
6 : 2 = 3 r 0, więc NWD = 2
Nie widzę jakichś problemów w jego stosowaniu.

sushi · Post autor: **sushi** » 4 paź 2006, o 19:48

Euklides dobrze chodzi, tylko jak się weźmie liczby "a" i "c"
postaci
a=b*c+0 to wtedy NWD(a,c)=c

suriel_k · Post autor: **suriel_k** » 4 paź 2006, o 19:51

sushi, no to lecimy dalej a czy możesz mi pomóc jeszcze w jednym ? każda liczba całkowita rozkłada się na iloczyn liczb pierwszych w pierwszej potędze. skąd wiadomo ile tych liczb do iloczynu ?i jak je znaleźć ? może na gg będzie łatwiej 2618722 ?

[ Dodano: 4 Październik 2006, 21:15 ]
no dobra dotarłem do tego trzeba zrobić rozkład kanoniczny i wtedy wyjdzie ile jest tych składników w pierwszej potędze. Ale czy ktoś zna strony z teorią ?

[ Dodano: 4 Październik 2006, 21:34 ]
Rogal, a czy możesz mi podać gdzie szukać teorii ? jestem z tych co to nie umieją liczyć ale muszę się nauczyć. i szukam pomocy

Rogal · Post autor: **Rogal** » 5 paź 2006, o 00:20

Teorii? Do Euklidesa? Polecałbym Wikipedię, tam powinno być. Jak nie to wszystkowiedzące Google.pl ułatwi Ci uczenie się ; )