خوارزمية إقليدس

خوارزمية إقليدس في نظرية الأعداد هي خوارزمية لحساب القاسم المشترك الأكبر لعددين طبيعيين ، تظهر أهميتها الأساسية في عدم حاجتنا لتحليل الرقمين كي نتمكن من حساب القاسم المشترك الأكبر لهما ، وتتميز بكونها إحدى أقدم الخوارزميات حيث ترجع إلى سنة 300 ق.م. .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

 وصف الخوارزمية

القاسم المشترك الأكبر لعددين طبيعيين A ، B يساوي القاسم المشترك الأكبر للعدد الثاني B و باقي قسمة A على B ، ونكرر العملية نفسها حتى يصبح باقي القسمة مساويا الصفر ، عندئذ يكون القاسم المشترك الأكبر هو العدد الآخر.

$\operatorname {GCD} (A,B)=\operatorname {GCD} (B,r)\cdots \cdots \operatorname {GCD} (N,0)$

حيث :

r باقي قسمة A على B

N هو القاسم المشترك الأكبر.

 مثال

القاسم المشترك الأكبر للعددين 252 و 198 :

252 = 198 * 1 + 54 ‘ أربع وخمسون هو باقي قسمة 252 على 198

فنجد القاسم المشترك للعددين 198 و 54

198 = 54 * 3 + 36 ‘ ست وثلاثون هو باقي القسمة.

نكرر العملية هذه المرة مع : 54 و 36

54 = 36 * 1 + 18

مرة أخرى : 36 = 18 * 2 + 0

هنا وصلنا للصفر فيكون العدد الثاني 18 هو القاسم المشترك الأكبر.

 خوارزمية إقليدس بلغة الحاسوب

التعليمات المطلوبة لتنفيذ خوارزمية إقليدس التي تقبل 0 على إي من مدخلاتها هي الحصول على القيمة المطلقة والتعيين والاختبارات النطقية والاستبدال والتكرار والطرح.

هذه الفقرة مازالت تحت الإنشاء!