Найти наименьшее общее кратное массива

[licenok]

1) при поиске НаибОД достаточно проверять числа не от 2 до min (a,b), а от 2 до min (a,b) /2.

не достаточно; НОД(7,14) например равен 7

Тогда уж вообще в одну строчку функцию можно написать:

Код: Выделить всё

int getNODab(int a, int b) // вычисляем НОД-наибольший общий делитель чмсел а и b
{  for (int i=min(a,b); i>0; i--) if (a%i==0 && b%i==0) return i; }

в крайнем случае вернёт 1

[licenok]

если располагать таблицей простых чисел, то можно значительно ускорить выполнение функции getNODab, особенно для больших чисел

предположим у нас есть достаточно большая для наших нужд таблица простых чисел 1 2 3 5 7 11 13 17 ...
и реализованы функции
long FindNearestSimpleNumberNotGreaterThan(long a); // возвращает ближайшее к a простое число не большее a
long GetPrev(long p); //возвращает ближайшее предыдущее к p простое число

тогда

Код: Выделить всё

long getNODab(long a, long b)
{
  long NOD = 1;
  long p,c;
  long maxp; //максимальное непроверенное число на предмет делятся ли на него a и b
  c = min(a,b);
  maxp = p = FindNearestSimpleNumberNotGreaterThan(c);}
  do
  {
    if (a%p==0 && b%p==0) 
    {NOD*=p; a=a/p; b=b/p;c = min(a,b);
     p = FindNearestSimpleNumberNotGreaterThan(c); p = min(p,maxp);}
    else {p = GetPrev(p); maxp=p;}
  }while(p>1);
  return NOD;
}

хотя вообще лучше переделать цикл на проверку с начала простых чисел (двигаться в массиве простых чисел не по убыванию, а по возрастанию; не GetPrev(p), а GetNext(p) соотвественно использовать)
для большинства пар (a,b) быстрее будет работать
но переписывать неохота ..

[BBB]

не достаточно; НОД(7,14) например равен 7

Ну да, переклинило малость, забыл, что тут, в отличие от проверки на простое число, можно на самое себя делить.
Но, к слову, такой "граничный эфект" проявляется в случае, когда одно (бОльшее) число нацело делится на другое (мЕньшее). В этом случае мЕньшее и будет Наибольш.ОД.
Так что, м/б имеет смысл первым шагом проверить такую делимость одного на другого.

[MDCI]

Можно исполозовать алгоритм евклида - http://ru.wikipedia.org/wiki/%D0%90%D0% ... 0%B4%D0%B0,

Код: Выделить всё

int CalcNOD(int Num1, int Num2)
{
int max=0;
int min=0;
int num0=0;

if (Num1 > Num2) 
{
max=Num1; 
min=Num2; 
}
else if (Num1 < Num2)
{
max=Num2; 
min=Num1; 
}
else 
{
num0=Num1;
return num0;
}

while (1)
{
   num0 = max - min;
   if (min > num0)
  {
     max=min;
     min=num0;
   }
   else if (min == num0)
   {
   return num0;
   }
   else if (min < num0)
   {
   max=num0;
   }
}
return 1;
}

Потом на это число делятся числитель и знаменатель
Наименьшее общее кратное можно найти по формуле (Википедия):
Наименьшее общее кратное