গণিতে, ইউক্লিডের অ্যালগরিদম হল দুটি সংখ্যার সর্বশ্রেষ্ঠ সাধারণ ভাজক (GCD) গণনার একটি পদ্ধতি, সবচেয়ে বড় সংখ্যা যা একটি অবশিষ্ট না রেখে উভয়কে ভাগ করে।
ইউক্লিডীয় অ্যালগরিদম এই নীতির উপর ভিত্তি করে যে দুটি সংখ্যার সর্বশ্রেষ্ঠ সাধারণ ভাজক পরিবর্তন হয় না যদি বড় সংখ্যাটি ছোট সংখ্যার সাথে তার পার্থক্য দ্বারা প্রতিস্থাপিত হয়।
উদাহরণস্বরূপ, 21 হল 252 এবং 105 এর GCD (যেমন 252 =21 × 12 এবং 105 =21 × 5), এবং একই সংখ্যা 21 হল 105 এবং 252 - 105 =147-এর GCD।
যেহেতু এই প্রতিস্থাপনটি দুটি সংখ্যার বড় সংখ্যাকে হ্রাস করে, এই প্রক্রিয়াটি পুনরাবৃত্তি করলে দুটি সংখ্যা সমান না হওয়া পর্যন্ত ধারাবাহিকভাবে ছোট জোড়া সংখ্যা পাওয়া যায়। যখন এটি ঘটে, তখন তারা আসল দুটি সংখ্যার GCD।
ধাপগুলিকে বিপরীত করে, GCD দুটি মূল সংখ্যার সমষ্টি হিসাবে প্রকাশ করা যেতে পারে যার প্রতিটিকে একটি ধনাত্মক বা ঋণাত্মক পূর্ণসংখ্যা দ্বারা গুণ করা হয়, যেমন, 21 =5 × 105 + (−2) × 252৷
আমাদের একটি জাভাস্ক্রিপ্ট ফাংশন লিখতে হবে যা দুটি সংখ্যা নেয় এবং তাদের 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
