ইউক্লিডের ভাগশেষ উপপাদ্য (Division Algorithm) এর সাহায্যে গসাগু নির্ণয়

আমরা দুটি সংখ্যার গসাগু (GCD-Greatest Common Common Divisor বা HCF-Highest Common Factor) বলতে বুঝি দুই বা তার অধিক সংখ্যার গসাগু হলো সেই বৃহত্তম সংখ্যা যাকে দিয়ে ঐ সংখ্যাগুলোকে নিঃশেষে ভাগ করা যায়।

ধরি দুটি সংখ্যা 12 ও 16।এদের ফ্যাক্টর গুলো হলও

1 x 12 = 12        1 x 16 = 16
2 x 6 = 12 2 x 8 = 16
3 x 4 = 12 4 x 4 = 16

এখানে 12 এর ফ্যাক্টর সমূহ 1,2,3,4,6,12 এবং 16 এর ফ্যাক্টর সমূহ 1,2,4,8,16.আর এই দুই সংখ্যার কমন ফ্যাক্টর সমূহ 1,2,4. সুতরাং 12 এবং 16 এর গসাগু হচ্ছে 4,কেননা 4 অন্যান্য কমন ফ্যাক্টর গুলোর মাঝে সবচেয়ে বড়।এছাড়াও আমরা প্রাইম ফ্যাক্টরাইজেশনের মাধ্যমেও গসাগু নির্ণয় করতে পারবো।আমরা জানি প্রত্যেকটি নাম্বারকেই এক বা একাধিক প্রাইম নাম্বারের গুণফল আকারে প্রকাশ করা যায়,আর এ ধর্মের সাহায্যেই আমরা দুটি সংখ্যার গসাগু নির্ণয় করতে পারবো।কিভাবে নির্ণয় করতে হবে তা একটু গুগল করলেই খুঁজে পাওয়া যাবে।আমি আর ঐ দিকে যাব না।এবার আমরা দেখবো কিভাবে ইউক্লিড এর ভাগশেষ উপপাদ্য ব্যাবহার করে গসাগু নির্নয় করা যায়। এবং গসাগু নির্নয় এর কোড(সি ভাষায়) আমি নিচে লিখে দিব।

আমরা চাইলেই দুটি সংখ্যা a ও b এর লসাগু বের করতে সংখ্যা দুটিকে x দিয়ে Mod(Modulus Operator ‘%’ ) করব।অর্থাৎ (a%x==0 এবং b%x==0) পরীক্ষা করব নিঃশেষে বিভাজ্য হয় কিনা।যদি হয় তাহলে আমরা গসাগু পেয়ে গেছি আর নিঃশেষে বিভাজ্য না হলে x এর মান 1 করে কমাতে থাকবো আর পরীক্ষা করতে থাকবো।এভাবে গসাগু নির্ণয় করাটা খুব সোজা হলেও আমাদের প্রোগ্রামটি ইফিশিয়েন্ট হবে না।কারণ দুটি সংখ্যা যদি খুব বড় হয় আর সহমৌলিক হয় তাহলে ঝামেলা পেকে যাবে।আর তাই আমরা ইউক্লিড এর ভাগশেষ উপপাদ্যের সাহায্যে গসাগু নির্ণয় করব।

আমরা জানি, ভাজ্য = ভাজক*ভাগফল + ভাগশেষ।এটাকে আমরা লিখতে পারি a=b*q+r (a,b,q,r সকলেই পূর্ণসংখ্যা) ।সুতরাং এখন আমরা বলতে পারি যে a,b এর গসাগু b,r এর লসাগু এর সমান হবে।আর এটিই হচ্ছে ইউক্লিড এর Algorithm এর মূল কথা।অর্থাৎ , GCD(a,b)=GCD(b,r)।এবার Algorithm টি কোডে লিখা যাক।

int GCD( int a, int b )
{
int temp;
if( a < b ) swap( a, b );
while( a % b != 0 ) {
temp = a;
a = b;
b = temp % b;
}
return b;
}

এখন আমরা খুব সহজ করে সি ভাষায় একটা প্রোগ্রাম লিখতে চেষ্টা করব যা আমাদের দুইটি সংখ্যার গসাগু এর মান বের করে দিতে পারবে আর প্রোগ্রামটিও বেশ ইফিশিয়েন্ট হবে।প্রথমে আমাদের দুটি জিনিস জানা লাগবে

  1. GCD(a,0)=a
  2. GCD(a,b)=GCD(b,a%b)

সুতরাং আমরা একটি লুপ এর সাহায্য নিব এবং a এর মান b আর b এর মান a%b বসিয়ে যাব যতক্ষণ না b এর মান শূন্য হয়। if(b==0) তবে GCD=a;

#include <stdio.h>
int main()
{
int a,b,c,gcd;
scanf("%d %d",&a,&b);
if(a==0)gcd=a;
else if(b==0) gcd=b;
else{
while(b!=0){
c=b;
b=a%b;
a=c;
}
gcd=a;
}
printf("GCD : %d\n",gcd);
return 0;
}

আপনারা চেষ্টা করে দেখবেন এই প্রোগ্রামটিকে আরও ইফিশিয়েন্ট করা যায় কিনা।আমরা চাইলে লসাগু (LCM) বের করতে পারবো।আমরা সকলেই জানি কিভাবে লসাগু বের করতে হয়।তারপরও আমি ছোট্ট একটা সূত্র লিখে দিচ্ছি যা ব্যাবহার করে আপনি খুব সহজেই ইউক্লিড এর উপপাদ্যের সাহায্যে নির্ণয় করা গসাগু থেকে লসাগু বের করতে পারবেন।সূত্রটি হচ্ছে

GCD(a,b)*LCM(a,b)=a*b

আমার ব্লগটি পড়ে যদি আপনি গসাগু ও লসাগু বের করা শিখতে পারেন তাহলে তাহলে UVa 11417 এবং UVa 11388 প্রব্লেম দুইটি সলভ করার চেষ্টা করতে পারেন।

আমি নিচে একটি ফ্লোচার্ট যুক্ত করব যা আপনাকে কোড লিখতে এবং নতুন ভাবে চিন্তা করতে সাহায্য করবে ।

ধন্যবাদ সবাইকে। হ্যাপি কোডিং :-)