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

Напомню, что НОД (наибольший общий делитель, 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);
}

---

теги: числа алгоритм c++

---

03.12.2012, 08:46; рейтинг: 11708