গাণিতিকভাবে, ইউক্লিডের অ্যালগরিদম দুটি সংখ্যার মહত্তম সাধারণ ভাজক (GCD) নির্ণয়ের একটি পদ্ধতি, অর্থাৎ সবচেয়ে বড় সেই সংখ্যা যা উভয়কে ভাগ করে অবশিষ্ট না রেখে।
ইউক্লিডিয়ান অ্যালগরিদম এই নীতির ওপর ভিত্তি করে যে: দুটি সংখ্যার GCD পরিবর্তন হয় না যদি বড় সংখ্যাটিকে তার পার্থক্য দিয়ে ছোট সংখ্যার সাথে প্রতিস্থাপন করা হয়।
উদাহরণস্বরূপ, ২১ হলো ২৫২ এবং ১০৫-এর GCD (কারণ ২৫২ = ২১ × ১২ এবং ১০৫ = ২১ × ৫), এবং একই সংখ্যা ২১ হলো ১০৫ এবং ২৫২ − ১০৫ = ১৪৭-এর GCD।
যেহেতু এই প্রতিস্থাপন বড় সংখ্যাটি কমানো করে, এই প্রক্রিয়া পুনরাবৃত্তি করলে dần dần ছোট ছোট জোড়া সংখ্যা পাওয়া যায় যতক্ষণ না দুটি সংখ্যা সমান হয়। যখন সেটি হয়, তখন সেগুলোই মূল দুটি সংখ্যার GCD।
ধাপগুলো উল্টে করলে GCD কে দুটি মূল সংখ্যার যোগফল হিসেবে প্রকাশ করা যায় যেখানে প্রতিটি একটি পজিটিভ বা নেগেটিভ পূর্ণসংখ্যা দিয়ে গুণিত, যেমন: ২১ = ৫ × ১০৫ + (−২) × ২৫২।
আমাদের একটি জাভাস্ক্রিপ্ট ফাংশন লিখতে হবে যা দুটি সংখ্যা নেবে এবং ইউক্লিডের অ্যালগরিদম ব্যবহার করে তাদের GCD নির্ণয় করবে।
উদাহরণ
নিচে কোড দেওয়া হলো:
const num1 = 252;
const num2 = 105;
const findGCD = (num1, num2) => {
let a = Math.abs(num1);
let b = Math.abs(num2);
while (a && b && a !== b) {
if(a > b){
[a, b] = [a - b, b];
}else{
[a, b] = [a, b - a];
};
};
return a || b;
};
console.log(findGCD(num1, num2));
আউটপুট
কনসোল আউটপুট:
21
