Най-голям общ делител
Най-големият общ делител на две цели числа е такова число, което дели без остатък и двете числа, като не съществува друго по-голямо число, което също да дели и двете числа без остатък.
За пример да вземем числата 24 и 32. Кой е техният най-голям общ делител? Търсим на първо място число, което дели и двете числа.
- Напр. числото 12 дели числото 24, но не дели числото 32, защото 32 / 12 е равно на 2,666…, което не е цяло число. Следователно числото 12 не може да е най-големият общ делител на числата 24 и 32.
- А какво да кажем за числото 4? То дели и двете числа, 24 / 4 е равно на 6 и 32 / 4 е равно на 8. Числото 4 е следователно първият ни кандидат. Съществува ли някое по-голямо число, което дели и двете числа?
- Числото 8 дели и числото 24, и числото 32 и освен това е по-голямо от числото 4.
- Не съществува друго число, по-голямо от 8, което да дели и двете числа. Числото 8 е следователно най-големият общ делител на числата 24 и 32.
Алгоритъм на Евклид за намиране на най-големия общ делител
Съществува доста прост начин да намерим най-големия общ делител на две числа с алгоритъма на Евклид. Нека в началото имаме две числа x и y, за които искаме да намерим най-големия общ делител. За пример ще опитаме с числата x = 50 и y = 35. После ще действаме така:
- Разделяме x / y и запомняме остатъка при делението. Този остатък отбелязваме като z. За нашия пример получаваме 50 / 35, което ни дава остатък z = 15.
- Сега разменяме променливите и в променливата x записваме стойността на y, а в y записваме стойността на z. Първоначалната стойност на x изхвърляме. След тази стъпка получаваме x = 35 и y = 15.
- Сега проверяваме дали y е равно на нула. Ако да, най-големият общ делител е числото x. Тъй като y не е равно на нула, продължаваме нататък и повтаряме целия алгоритъм отново от първата точка.
- Отново делим x / y, т.е. делим 35 / 15, което ни дава остатък при делението z = 5.
- Извършваме размяна на променливите, т.е. получаваме x = 15 и y = 5. Тъй като y не е равно на нула, продължаваме нататък.
- Делим x / y, т.е. делим 15 / 5. Остатъкът при делението е z = 0.
- Разменяме променливите и получаваме x = 5 и y = 0.
- В този момент y = 0 и алгоритъмът завършва. Най-големият общ делител е числото x = 5.
Важното е, че редът на числата няма значение. Ако бяхме разменили числата от примера, щяхме да получим двойката x = 35 и y = 50. Алгоритъмът щеше да е същият:
- Разделяме x / y, т.е. делим 35 / 50, което ни дава остатък z = 35.
- Разменяме променливите x = 50 и y = 35.
- Виждаме, че след тази стъпка просто сме разменили съдържанието на променливите x и y помежду им…
Калкулатор
Този калкулатор ти пресмята най-големия общ делител.