യൂക്ലിഡിന്റെ അൽഗൊരിതം

ഇംഗ്ലീഷ് വിലാസം

http://ml.wikipedia.org/wiki/Euclidean_algorithm

ഗണിതശാസ്ത്രത്തിൽ ഉത്തമ സാധാരണ ഘടകം (ഉ.സാ.ഘ) കണ്ടെത്താനുള്ള ഫലപ്രദമായ ഒരു രീതിയാണ്‌ യൂക്ലിഡിന്റെ അൽഗോരിതം.

ഗ്രീക്ക് ഗണിത ശാസ്ത്രജ്ഞനായ യൂക്ലിഡിന്റെ പേരിലാണ് ഈ രീതി അറിയപ്പെടുന്നത്. അദ്ദേഹത്തിന്റെ എലിമെന്റ്സിലെ VII, IX പുസ്തകങ്ങളിൽ അദ്ദേഹം ഇത് വിവരിച്ചിരിക്കുന്നു.

രണ്ടു സംഖ്യകളുടെ ഉ സാ ഘ എന്നത് ആ രണ്ടു സംഖ്യകളെയും പൊതുവായി പൂർണമായും ഹരിക്കാവുന്ന ഏറ്റവും ഉയർന്ന സംഖ്യായാണ്. രണ്ടു സംഖ്യകളിൽ ചെറുത് വലുതിൽ നിന്ന് കുറച്ചാൽ അവയുടെ ഉ സാ ഘ മാറില്ല എന്നാ തത്ത്വത്തിൽ അധിഷ്ടിതമാണ് യുക്ലിടിന്റെ അല്ഗോരിതം .ഉദാഹരണത്തിന് 252,105 എന്നീ സംഖ്യകളുടെ ഉ സാ ഘ 21 ആണ്(252 = 21 × 12; 105 = 21 × 5). ഇനി ഇവയിൽ ചെറിയ സംഖ്യ ആയ 105 വലിയ സംഖ്യ ആയ 252 -ൽ നിന്ന് കുറച്ചാൽ കിട്ടുന്ന 147 എന്ന സംഖ്യയുടെയും 105 ന്റെയും ഉ സാ ഘ 21 തന്നെ ആണ് . ഈ പ്രക്രിയ ഏതെങ്കിലും ഒരു സംഖ്യ പൂജ്യമാവുന്നത് വരെ തുടർന്നാൽ മിച്ചം കിട്ടുന്ന സംഖ്യ ആയിരിക്കും തുടക്കത്തിലെ സംഖ്യകളുടെ ഉ സാ ഘ.

അൽഗരിതം

int FindGCD(int p, int q)
{
        if (p == 0) return q;
        else return FindGCD(q%p,p);
}