الگوریتم اقلیدس

الگوریتم اقلیدس یک الگوریتم برای محاسبهٔ بزرگ‌ترین مقسوم علیه مشترک (ب.م.م.) است که اولین بار توسط اقلیدس در کتاب اصول اقلیدس شرح داده شده است. در این روش، برای محاسبهٔ ب.م.م. دو عدد x و y که به صورت نمایش داده می‌شود، چنین عمل می‌شود (فرض بر این است که x از y بزرگتر است، اگر چه در حالت برعکس نیز، صرفاً با تغییر نام x و y این روش قابل استفاده خواهد بود):

1. از x به اندازهٔ y کم کن، و مقدار جدید را به جای x جایگذاری کن
2. قدم بالا را آن قدر تکرار کن تا x از y کوچک‌تر شود
3. جای x و y را عوض کن و قدم‌ها بالا را تکرار کن، تا وقتی که مقدار x صفر شود؛ در این حالت، مقدار y برابر با ب.م.م. دو عدد x و y خواهد بود.

اگر ب.م.م دو عدد برابر با یک شود ان دو عدد نسبت به هم اول هستند که با آن متباین گفته می شود.

راه های دیگری برای بدست اوردن (ب م م) است که شرح می دهم . 1- اگر عدد کوچک تر بر عدد بزرگ تر تقسیم شود و باقی مانده صفر صفر شود عدد کوچک تر (ب م م) است . 2- اگر هر دو عدد اعداد اول بودند (ب م م) آنها برابر با یک است . 3- اگر هر دو عدد متوالی بودند باز هم برابر با یک است .

به عنوان نمونه، اگر x برابر ۷۰ و y برابر ۲۵ باشد، مراحل کار چنین خواهد بود:

ب.م.م.(۲۵و۷۰) ← ب.م.م.(۲۵و۴۵) ← ب.م.م.(۲۵و۲۰) ← ب.م.م.(۲۰و۲۵)
← ب.م.م.(۲۰و۵) ← ب.م.م.(۵و۲۰) ← ب.م.م.(۵و۱۵) ← ب.م.م.(۵و۱۰)
← ب.م.م.(۵و۵) ← ب.م.م.(۵و۰) ← ب.م.م. = ۵

مثالی از این الگوریتم به زبان سی

int gcd(int x, int y){
   if (y == 0) {
       return x;
   } else {
       return gcd(y, x % y);
   }
{