НОД и НОК для массива

Напомню, что НОД (наибольший общий делитель, GCD) для натуральных чисел A и B - максимальное из чисел, на которые A и B делятся без остатка, НОК (наименьшее общее кратное, LCM) - минимальное из чисел, которые делятся на A и B без остатка. Можно реализовать простой и удобный алгоритм поиска НОД и НОК для пары чисел, а для массива натуральных чисел у народа почему-то вызвало затруднения. Между тем, вот такое решение кажется мне простым и правильным:

#include <stdio.h>

//Реализация для 2 чисел
long int nod (int x, int y) { return (x?nod(y%x,x):y); }
long int nok (int x, int y) { return x*y/nod(x,y); }
//и вернуть nok(x,y) или nod(x,y)

void main () {
 const int n=5;
 int a[n]={24,36,144,48,72},i;
 //НОД для массива:
 long int nd=a[0];
 for (i=1; i<n; i++) nd=nod((nd<a[i]?nd:a[i]),(nd<a[i]?a[i]:nd));
 printf ("\nNOD=%ld",nd);
 //НОК для массива:
 long int nk=1;
 for (i=0; i<n; i++) nk=nok(nk,a[i]);
 printf ("\nNOK=%ld",nk);
}

Или с выводом через <iostream>:

#include <iostream>
using namespace std;

long int nod(long int x, long int y) { return (x ? nod(y % x, x) : y); }
long int nok(long int x, long int y) { return x * y / nod(x, y); }

int main() {
 const int n = 5;
 long int a[n] = { 24, 36, 144, 48, 72 }, i;
 //НОД для массива:
 long int nd = a[0];
 for (i = 1; i < n; i++) nd = nod((nd < a[i] ? nd : a[i]), (nd < a[i] ? a[i] : nd));
 cout << "NOD = " << nd << endl;
 //НОК для массива:
 long int nk = 1;
 for (i = 0; i < n; i++) nk = nok(nk, a[i]);
 cout << "NOK = " << nk << endl;
 return 0; 
}

P.S. Начиная со стандарта C++17, можно воспользоваться стандартными средствами, смотрите в комментарии к программе как подключить компиляцию стандарта C++17 в консольном проекте Visual Studio 2019.

//Включить в свойствах проекта поддержку стандарта C++17:
// Project, Properties, C/C++, Language, C++ Language Standard, ISO C++17 (/std:c++17)
#include <iostream>
#include <numeric>
using namespace std;

int main() {
 int n = 24, m = 36;
 cout << gcd(n, m) << endl; //НОД, https://en.wikipedia.org/wiki/Greatest_common_divisor
 cout << lcm(n, m) << endl; //НОК, https://en.wikipedia.org/wiki/Least_common_multiple
 return 0;
}

03.12.2012, 08:46 [16656 просмотров]