Algorithms/LCM

المضاعف المشترك الأصغر (Least Common Multiple) لعددين هو أصغر عدد يمكن قسمته بواسطة كلا العددين. فعلى سبيل المثال المضاعف المشترك الأصغر للعددين 15 و 20 هو 60 وللعددين 5 و7 هو 35.

أبسط طريقة لإيجاد المضاعف المشترك الأصغر هي إيجاد جميع العوامل الأولية للأعداد، ثم توحيد جميع العوامل الموجودة في كلا الرقمين، ثم إعادة حاصل الضرب العوامل الموحّدة.

هناك عدة طرق لإيجاد المضاعف المشترك الأصغر نذكر منها:

إيجاد المضاعف المشترك الأصغر باستخدام القاسم المشترك الأكبر

تستند هذه الطريقة على الصيغة الرياضية التالية والتي تربط بين المضاعف المشترك الأصغر والقاسم المشترك الأكبر:

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

   LCM(a, b) = (a x b) / GCD(a, b)

تعرض الأمثلة التالية طريقة إيجاد المضاعف المشترك الأصغر في عدد من لغات البرمجة:

• C++‎:

#include <iostream> 
using namespace std; 

// دالة تعاودية لإيجاد القاسم المشترك الأكبر للعددين المعطيين
class gfg 
{ 
public : int gcd(int a, int b){ 
	if (a == 0) 
		return b; 
	return gcd(b % a, a); 
} 


// تعيد الدالة المضاعف المشترك الأصغر للعددين المعطيين
int lcm(int a, int b) 
{ 
	return (a*b)/gcd(a, b); 
} 
} ; 
// اختبار الدوال السابقة
int main() 
{ 
	gfg g; 
	int a = 15, b = 20; 
	cout<<"LCM of "<<a<<" and "<<b<<" is "<<g.lcm(a, b); 
	return 0; 
}

• بايثون:

# دالة تعاودية لإيجاد القاسم المشترك الأكبر للعددين المعطيين 
def gcd(a,b): 
	if a == 0: 
		return b 
	return gcd(b % a, a) 

# تعيد الدالة المضاعف المشترك الأصغر للعددين المعطيين
def lcm(a,b): 
	return (a*b) / gcd(a,b) 

# اختبار الدوال السابقة
a = 15
b = 20
print('LCM of', a, 'and', b, 'is', lcm(a, b))

• جافا:

class Test 
{ 
	// دالة تعاودية لإيجاد القاسم المشترك الأكبر للعددين المعطيين
	static int gcd(int a, int b) 
	{ 
	if (a == 0) 
		return b; 
	return gcd(b % a, a); 
	} 
	
	// تعيد الدالة المضاعف المشترك الأصغر للعددين المعطيين
	static int lcm(int a, int b) 
	{ 
		return (a*b)/gcd(a, b); 
	} 
	
	// اختبار الدوال السابقة
	public static void main(String[] args) 
	{ 
		int a = 15, b = 20; 
		System.out.println("LCM of " + a +" and " + b + " is " + lcm(a, b)); 
	} 
}

إيجاد المضاعف المشترك الأصغر دون استخدام القاسم المشترك الأكبر

تبدأ هذه الطريقة مع الرقم الأكبر بين الرقمين المعطيين، وتستمر في إضافته إلى نفسه إلى أن يقبل الناتج القسمة على العدد الأصغر.

الأمثلة:

• C++‎:

#include <bits/stdc++.h> 
using namespace std; 

// تعيد الدالة المضاعف المشترك الأصغر للعددين المعطيين
int findLCM(int a, int b) 
{ 
	int lar = max(a, b); 
	int small = min(a, b); 
	for (int i = lar; ; i += lar) { 
		if (i % small == 0) 
			return i; 
	} 
} 

// اختبار الدالة السابقة
int main() 
{ 
	int a = 5, b = 7; 
	cout << "LCM of " << a << " and "
		<< b << " is " << findLCM(a, b); 
	return 0; 
}

• بايثون:

import sys 

# تعيد الدالة المضاعف المشترك الأصغر للعددين المعطيين
def findLCM(a, b): 

	lar = max(a, b) 
	small = min(a, b) 
	i = lar 
	while(1) : 
		if (i % small == 0): 
			return i 
		i += lar 
	
# اختبار الدالة السابقة
a = 5
b = 7
print("LCM of " , a , " and ", 
				b , " is " , 
	findLCM(a, b), sep = "")

• جافا:

import java.io.*; 
import java.lang.*; 

class GfG { 
	
	// تعيد الدالة المضاعف المشترك الأصغر للعددين المعطيين
	public static int findLCM(int a, int b) 
	{ 
		int lar = Math.max(a, b); 
		int small = Math.min(a, b); 
		for (int i = lar; ; i += lar) { 
			if (i % small == 0) 
				return i; 
		} 
	} 
	
	// اختبار الدالة السابقة
	public static void main(String [] argc) 
	{ 
		int a = 5, b = 7; 
		System.out.println( "LCM of " + a + " and "
			+ b + " is " + findLCM(a, b)); 
		
	} 
}

إيجاد المضاعف المشترك الأصغر لمجموعة من الأعداد

لا يمكن استخدام العلاقة التي تربط المضاعف المشترك الأصغر بالقاسم المشترك الأكبر (المذكورة أعلاه) لإيجاد المضاعف المشترك الأصغر لأكثر من عددين، ولكن يمكن توسيع العلاقة السابقة للقيام بذلك. فلو فرضنا أن لدينا المصفوفة arr[]‎ والتي تحتوي على n من الأعداد التي نرغب في حساب المضاعف المشترك الأصغر لها، فإنّ خطوات الخوارزمية ستكون كما يلي:

1. إسناد قيمة العنصر الأول في المصفوفة إلى المتغير الذي سيحمل قيمة الجواب: ans = arr[0]‎.
2. المرور على جميع العناصر في المصفوفة arr[]‎ أي من i = 1 إلى i = n-1. وفي الدورة i يكون ‎ans = LCM(arr[0], arr[1], …….., arr[i-1])‎، ويمكن تنفيذ هذا بسهولة وذلك لأنّ ‎LCM(arr[0], arr[1], …., arr[i]) = LCM(ans, arr[i])‎، وبهذا يمكن تنفيذ ‎ans = LCM(ans, arr[i]) = ans x arr[i] / gcd(ans, arr[i])‎ في كل دورة من دورات الحلقة التكرارية.

تعرض الأمثلة التالية طريقة تنفيذ الخوارزمية في عدد من لغات البرمجة:

• C++‎:

#include <bits/stdc++.h> 
using namespace std; 

typedef long long int ll; 

// دالة مساعدة لإيجاد القاسم المشترك الأكبر للعددين المعطيين
int gcd(int a, int b) 
{ 
	if (b == 0) 
		return a; 
	return gcd(b, a % b); 
} 

// تعيد الدالة المضاعف المشترك الأصغر لعناصر المصفوفة المعطاة
ll findlcm(int arr[], int n) 
{ 
	// تهيئة الجواب
	ll ans = arr[0]; 

	// تكون قيمة الجواب هي المضاعف المشترك الأصغر للعددين
	// arr[0], .. arr[i]
	// i بعد الدورة
	for (int i = 1; i < n; i++) 
		ans = (((arr[i] * ans)) / 
				(gcd(arr[i], ans))); 

	return ans; 
} 

// اختبار الدوال السابقة
int main() 
{ 
	int arr[] = { 2, 7, 3, 9, 4 }; 
	int n = sizeof(arr) / sizeof(arr[0]); 
	printf("%lld", findlcm(arr, n)); 
	return 0; 
}

• بايثون

def find_lcm(num1, num2): 
	if(num1>num2): 
		num = num1 
		den = num2 
	else: 
		num = num2 
		den = num1 
	rem = num % den 
	while(rem != 0): 
		num = den 
		den = rem 
		rem = num % den 
	gcd = den 
	lcm = int(int(num1 * num2)/int(gcd)) 
	return lcm 
	
l = [2, 7, 3, 9, 4] 

num1 = l[0] 
num2 = l[1] 
lcm = find_lcm(num1, num2) 

for i in range(2, len(l)): 
	lcm = find_lcm(lcm, l[i]) 
	
print(lcm)

• جافا:

class GFG {
    
    // دالة مساعدة لإيجاد القاسم المشترك الأكبر للعددين المعطيين
    
    public static int gcd(int a, int b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    } 
    
    // تعيد الدالة المضاعف المشترك الأصغر لعناصر المصفوفة المعطاة
    public static int findlcm(int arr[], int n) {
        // تهيئة الجواب
        int ans = arr[0];
        
        // تكون قيمة الجواب هي المضاعف المشترك الأصغر للعددين
		// arr[0], .. arr[i]
		// i بعد الدورة
        for (int i = 1; i < n; i++)
            ans = (((arr[i] * ans)) / (gcd(arr[i], ans)));
        
        return ans;
    }
    
    // اختبار الدوال السابقة
	public static void main (String[] args) {
		int arr[] = {2, 7, 3, 9, 4};
		int n = arr.length;
		System.out.println(findlcm(arr, n));
	}
}

مصادر

• صفحة Program to find LCM of two numbers في توثيق الخوارزميات في موقع GeeksforGeeks.
• صفحة Program to find LCM of 2 numbers without using GCD في توثيق الخوارزميات في موقع GeeksforGeeks.
• صفحة LCM of given array elements في توثيق الخوارزميات في موقع GeeksforGeeks.