Как найти НОК и НОД двух чисел на нескольких языках

Дядя Влад

Математика – важная часть программирования и информатики. Это ядро ​​любого хорошего алгоритма, обеспечивающее аналитические навыки, необходимые для программирования.

Математические алгоритмы также являются очень важной темой для собеседований по программированию. В этой статье вы узнаете, как найти GCD и LCM двух чисел с помощью C ++, Python, C и JavaScript.

Как найти НОД двух чисел

Наибольший общий делитель (GCD) или наивысший общий делитель (HCF) двух чисел – это наибольшее положительное целое число, которое идеально делит два заданных числа. Вы можете найти НОД двух чисел, используя алгоритм Евклида.

В алгоритме Евклида большее число делится на меньшее число, затем меньшее число делится на остаток от предыдущей операции. Этот процесс повторяется до тех пор, пока остаток не станет 0.

Например, если вы хотите найти НОД 75 и 50, вам необходимо выполнить следующие действия:

  • Разделите большее число на меньшее и возьмите остаток.
 75 % 50 = 25
  • Разделите меньшее число на остаток от предыдущей операции.
 50 % 25 = 0
  • Теперь остаток становится 0, таким образом, НОД 75 и 50 равны 25.

Программа на C ++ для поиска НОД двух чисел

Ниже приведена программа на C ++ для поиска НОД двух чисел:

 // C++ program to find GCD/HCF of 2 numbers
 #include <iostream>
 using namespace std;
 // Recursive function to find GCD/HCF of 2 numbers
 int calculateGCD(int num1, int num2)
 {
 if(num2==0)
 {
 return num1;
 }
 else
 {
 return calculateGCD(num2, num1%num2);
 }
 }
 // Driver Code
 int main()
 {
 int num1 = 34, num2 = 22;
 cout << "GCD of " << num1 << " and " << num2 << " is " << calculateGCD(num1, num2) << endl;
 int num3 = 10, num4 = 2;
 cout << "GCD of " << num3 << " and " << num4 << " is " << calculateGCD(num3, num4) << endl;
 int num5 = 88, num6 = 11;
 cout << "GCD of " << num5 << " and " << num6 << " is " << calculateGCD(num5, num6) << endl;
 int num7 = 40, num8 = 32;
 cout << "GCD of " << num7 << " and " << num8 << " is " << calculateGCD(num7, num8) << endl;
 int num9 = 75, num10 = 50;
 cout << "GCD of " << num9 << " and " << num10 << " is " << calculateGCD(num9, num10) << endl;
 return 0;
 }

Выход:

 GCD of 34 and 22 is 2
 GCD of 10 and 2 is 2
 GCD of 88 and 11 is 11
 GCD of 40 and 32 is 8
 GCD of 75 and 50 is 25

Программа Python для поиска НОД двух чисел

Ниже приведена программа Python для поиска НОД двух чисел:

По теме: что такое рекурсия и как ее использовать?

 # Python program to find GCD/HCF of 2 numbers
 def calculateGCD(num1, num2):
 if num2==0:
 return num1
 else:
 return calculateGCD(num2, num1%num2)
 # Driver Code
 num1 = 34
 num2 = 22
 print("GCD of", num1, "and", num2, "is", calculateGCD(num1, num2))
 num3 = 10
 num4 = 2
 print("GCD of", num3, "and", num4, "is", calculateGCD(num3, num4))
 num5 = 88
 num6 = 11
 print("GCD of", num5, "and", num6, "is", calculateGCD(num5, num6))
 num7 = 40
 num8 = 32
 print("GCD of", num7, "and", num8, "is", calculateGCD(num7, num8))
 num9 = 75
 num10 = 50
 print("GCD of", num9, "and", num10, "is", calculateGCD(num9, num10))

Выход:

 GCD of 34 and 22 is 2
 GCD of 10 and 2 is 2
 GCD of 88 and 11 is 11
 GCD of 40 and 32 is 8
 GCD of 75 and 50 is 25

Программа на C для поиска НОД двух чисел

Ниже приведена программа на языке C для поиска НОД двух чисел:

 // C program to find GCD/HCF of 2 numbers
 #include <stdio.h>
 // Recursive function to find GCD/HCF of 2 numbers
 int calculateGCD(int num1, int num2)
 {
 if(num2==0)
 {
 return num1;
 }
 else
 {
 return calculateGCD(num2, num1%num2);
 }
 }
 // Driver Code
 int main()
 {
 int num1 = 34, num2 = 22;
 printf("GCD of %d and %d is %d ⁠⁠n" , num1 , num2, calculateGCD(num1, num2));
 int num3 = 10, num4 = 2;
 printf("GCD of %d and %d is %d ⁠⁠n" , num3 , num4, calculateGCD(num3, num4));
 int num5 = 88, num6 = 11;
 printf("GCD of %d and %d is %d ⁠⁠n" , num5 , num6, calculateGCD(num5, num6));
 int num7 = 40, num8 = 32;
 printf("GCD of %d and %d is %d ⁠⁠n" , num7 , num8, calculateGCD(num7, num8));
 int num9 = 75, num10 = 50;
 printf("GCD of %d and %d is %d ⁠⁠n" , num9 , num10 , calculateGCD(num9, num10));
 return 0;
 }

Выход:

 GCD of 34 and 22 is 2
 GCD of 10 and 2 is 2
 GCD of 88 and 11 is 11
 GCD of 40 and 32 is 8
 GCD of 75 and 50 is 25

Программа на JavaScript для поиска НОД двух чисел

Ниже приведена программа на JavaScript для поиска НОД двух чисел:

 // JavaScript program to find GCD/HCF of 2 numbers
 // Recursive function to find GCD/HCF of 2 numbers
 function calculateGCD(num1, num2) {
 if(num2==0)
 {
 return num1;
 }
 else
 {
 return calculateGCD(num2, num1%num2);
 }
 }
 // Driver Code
 var num1 = 34, num2 = 22;
 document.write("GCD of " + num1 + " and " + num2 + " is " + calculateGCD(num1, num2) + "<br>");
 var num3 = 10, num4 = 2;
 document.write("GCD of " + num3 + " and " + num4 + " is " + calculateGCD(num3, num4) + "<br>");
 var num5 = 88, num6 = 11;
 document.write("GCD of " + num5 + " and " + num6 + " is " + calculateGCD(num5, num6) + "<br>");
 var num7 = 40, num8 = 32;
 document.write("GCD of " + num7 + " and " + num8 + " is " + calculateGCD(num7, num8) + "<br>");
 var num9 = 75, num10 = 50;
 document.write("GCD of " + num9 + " and " + num10 + " is " + calculateGCD(num9, num10) + "<br>");

Выход:

 GCD of 34 and 22 is 2
 GCD of 10 and 2 is 2
 GCD of 88 and 11 is 11
 GCD of 40 and 32 is 8
 GCD of 75 and 50 is 25

Как найти НОК двух чисел

Наименьшее общее кратное (НОК) двух чисел – это наименьшее положительное целое число, которое полностью делится на два заданных числа. Вы можете найти НОК двух чисел, используя следующую математическую формулу:

 num1 * num2 = LCM(num1, num2) * GCD(num1, num2)
 LCM(num1, num2) = (num1 * num2) / GCD(num1, num2)

Чтобы найти НОК двух чисел программным способом, вам нужно использовать функцию, чтобы найти НОД двух чисел.

Связанный: Как сложить и вычесть две матрицы в C ++, Python и JavaScript

Программа на C ++ для поиска НОК двух чисел

Ниже приведена программа на C ++ для поиска НОК двух чисел:

 // C++ program to find LCM of 2 numbers
 #include <iostream>
 using namespace std;
 // Recursive function to find LCM of 2 numbers
 int calculateGCD(int num1, int num2)
 {
 if(num2==0)
 {
 return num1;
 }
 else
 {
 return calculateGCD(num2, num1%num2);
 }
 }
 int calculateLCM(int num1, int num2)
 {
 return (num1 / calculateGCD(num1, num2)) * num2;
 }
 // Driver Code
 int main()
 {
 int num1 = 34, num2 = 22;
 cout << "LCM of " << num1 << " and " << num2 << " is " << calculateLCM(num1, num2) << endl;
 int num3 = 10, num4 = 2;
 cout << "LCM of " << num3 << " and " << num4 << " is " << calculateLCM(num3, num4) << endl;
 int num5 = 88, num6 = 11;
 cout << "LCM of " << num5 << " and " << num6 << " is " << calculateLCM(num5, num6) << endl;
 int num7 = 40, num8 = 32;
 cout << "LCM of " << num7 << " and " << num8 << " is " << calculateLCM(num7, num8) << endl;
 int num9 = 75, num10 = 50;
 cout << "LCM of " << num9 << " and " << num10 << " is " << calculateLCM(num9, num10) << endl;
 return 0;
 }

Выход:

 LCM of 34 and 22 is 374
 LCM of 10 and 2 is 10
 LCM of 88 and 11 is 88
 LCM of 40 and 32 is 160
 LCM of 75 and 50 is 150

Программа Python для поиска НОК двух чисел

Ниже приведена программа Python для поиска НОК двух чисел:

 # Python program to find LCM of 2 numbers
 def calculateGCD(num1, num2):
 if num2==0:
 return num1
 else:
 return calculateGCD(num2, num1%num2)
 def calculateLCM(num1, num2):
 return (num1 // calculateGCD(num1, num2)) * num2
 # Driver Code
 num1 = 34
 num2 = 22
 print("LCM of", num1, "and", num2, "is", calculateLCM(num1, num2))
 num3 = 10
 num4 = 2
 print("LCM of", num3, "and", num4, "is", calculateLCM(num3, num4))
 num5 = 88
 num6 = 11
 print("LCM of", num5, "and", num6, "is", calculateLCM(num5, num6))
 num7 = 40
 num8 = 32
 print("LCM of", num7, "and", num8, "is", calculateLCM(num7, num8))
 num9 = 75
 num10 = 50
 print("LCM of", num9, "and", num10, "is", calculateLCM(num9, num10))

Выход:

 LCM of 34 and 22 is 374
 LCM of 10 and 2 is 10
 LCM of 88 and 11 is 88
 LCM of 40 and 32 is 160
 LCM of 75 and 50 is 150

Программа на C для поиска НОК двух чисел

Ниже приведена программа на языке C для поиска НОК двух чисел:

 // C program to find LCM of 2 numbers
 #include <stdio.h>
 // Recursive function to find LCM of 2 numbers
 int calculateGCD(int num1, int num2)
 {
 if(num2==0)
 {
 return num1;
 }
 else
 {
 return calculateGCD(num2, num1%num2);
 }
 }
 int calculateLCM(int num1, int num2)
 {
 return (num1 / calculateGCD(num1, num2)) * num2;
 }
 // Driver Code
 int main()
 {
 int num1 = 34, num2 = 22;
 printf("LCM of %d and %d is %d ⁠n" , num1 , num2, calculateLCM(num1, num2));
 int num3 = 10, num4 = 2;
 printf("LCM of %d and %d is %d ⁠n" , num3 , num4, calculateLCM(num3, num4));

 int num5 = 88, num6 = 11;
 printf("LCM of %d and %d is %d ⁠n" , num5 , num6, calculateLCM(num5, num6));
 int num7 = 40, num8 = 32;
 printf("LCM of %d and %d is %d ⁠n" , num7 , num8, calculateLCM(num7, num8));
 int num9 = 75, num10 = 50;
 printf("LCM of %d and %d is %d ⁠n" , num9 , num10 , calculateLCM(num9, num10));
 return 0;
 }

Выход:

 LCM of 34 and 22 is 374
 LCM of 10 and 2 is 10
 LCM of 88 and 11 is 88
 LCM of 40 and 32 is 160
 LCM of 75 and 50 is 150

Программа на JavaScript для поиска НОК двух чисел

Ниже приведена программа на JavaScript для поиска НОК двух чисел:

 // JavaScript program to find LCM of 2 numbers
 // Recursive function to find LCM of 2 numbers
 function calculateGCD(num1, num2) {
 if(num2==0)
 {
 return num1;
 }
 else
 {
 return calculateGCD(num2, num1%num2);
 }
 }
 function calculateLCM(num1, num2)
 {
 return (num1 / calculateGCD(num1, num2)) * num2;
 }
 // Driver Code
 var num1 = 34, num2 = 22;
 document.write("LCM of " + num1 + " and " + num2 + " is " + calculateLCM(num1, num2) + "<br>");
 var num3 = 10, num4 = 2;
 document.write("LCM of " + num3 + " and " + num4 + " is " + calculateLCM(num3, num4) + "<br>");
 var num5 = 88, num6 = 11;
 document.write("LCM of " + num5 + " and " + num6 + " is " + calculateLCM(num5, num6) + "<br>");
 var num7 = 40, num8 = 32;
 document.write("LCM of " + num7 + " and " + num8 + " is " + calculateLCM(num7, num8) + "<br>");
 var num9 = 75, num10 = 50;
 document.write("LCM of " + num9 + " and " + num10 + " is " + calculateLCM(num9, num10) + "<br>");

Выход:

 LCM of 34 and 22 is 374
 LCM of 10 and 2 is 10
 LCM of 88 and 11 is 88
 LCM of 40 and 32 is 160
 LCM of 75 and 50 is 150

Узнать больше о математических алгоритмах

Математические алгоритмы играют жизненно важную роль в программировании. Целесообразно знать о некоторых основных программах, основанных на математических алгоритмах, таких как ситовые алгоритмы, простое факторизация, делители, числа Фибоначчи, вычисления nCr и т. Д.

В настоящее время функциональное программирование находится на вершине тенденций программирования в Интернете. Парадигма функционального программирования рассматривает вычисления как математические функции, и эта концепция очень полезна в программировании. Вы должны знать о функциональном программировании и о том, какие языки программирования поддерживают его, чтобы стать наиболее эффективным программистом.