Здравствуйте Vladik, Вы писали:

V>Привет!

V>Я, конечно, извиняюсь... Но может напомните, а?

    int a = 18;
    int b = 45;
    int c;

    while( b != 0)
    {
      c = a % b;
      a = b;
      b = c;
    }
printf("Результат: %i\n",a);

Здравствуйте Vladik, Вы писали:

V>Привет!

V>Я, конечно, извиняюсь... Но может напомните, а?
Классический, со школы:
Раскладываем на простые множители и все совпавшие перемножаем, полученое число и есть ответ.
З.Ы. если берем число 8 разложение = 2*2*2
Другоих алгоритмов вот так сходу и не припомню...

Здравствуйте Vladik, Вы писали:

V>Я, конечно, извиняюсь... Но может напомните, а?

http://alglib.chat.ru/theoryn/

Здравствуйте Vladik, Вы писали:

V>Привет!

V>Я, конечно, извиняюсь... Но может напомните, а?

http://algolist.manual.ru/maths/teornum/nod.php

Здравствуйте Vladik, Вы писали:

V>Привет!

V>Я, конечно, извиняюсь... Но может напомните, а?

я думаю так вот например 2 числа 150 и 125, раскладываешь их на множители (простые чила, кот. делятся только на елиницу и само на себя), получаешь:
150 = 5 * 5 * 3 * 2
125 = 5 * 5 * 5
ну и точно не припомню, но исключаешь в 150 3 * 2 (их просто нет в 125), а в 125 исключаешь одну 5, получаем 25, иначе говоря, в разложенных числах надо оставить те, которые есть в обоих (5*5)

Привет!

Я, конечно, извиняюсь... Но может напомните, а?

Здравствуйте, NikNRudoy и Hacker_Delphi, Вы писали:

NNR>раскладываешь их на множители (простые чила, кот. делятся только на елиницу и само на себя)
...
HD>Раскладываем на простые множители и все совпавшие перемножаем, полученое число и есть ответ.
HD>З.Ы. если берем число 8 разложение = 2*2*2
HD>Другоих алгоритмов вот так сходу и не припомню...

Если вам удастся придумать эффективный алгоритм разложения числа на простые множители, то вам гарантированны слава, деньги и т.д. И, пожалуй, куча "троечек" к тем нулям, которые вы успели схватить.

Здравствуйте vladsm, Вы писали:

V>Если вам удастся придумать эффективный алгоритм разложения числа на простые множители, то вам гарантированны слава, деньги и т.д. И, пожалуй, куча "троечек" к тем нулям, которые вы успели схватить.
Ну... меня же просили тока простой алгоритм... я ж не говорил, что он — оптимален

Здравствуйте Hacker_Delphi, Вы писали:

HD>Ну... меня же просили тока простой алгоритм... я ж не говорил, что он — оптимален

А алгоритм Евклида со школы уже позабылся?

Здравствуйте achp, Вы писали:

A>Здравствуйте Hacker_Delphi, Вы писали:

HD>>Ну... меня же просили тока простой алгоритм... я ж не говорил, что он — оптимален

A>А алгоритм Евклида со школы уже позабылся?
угу давно ето было

Здравствуйте Hacker_Delphi, Вы писали:

A>>А алгоритм Евклида со школы уже позабылся?
HD>угу давно ето было

Ну,.. надо же держать себя в форме

Здравствуйте Vladik, Вы писали:

V>Привет!

V>Я, конечно, извиняюсь... Но может напомните, а?

int mindn (int x,int y)                                                                                                                
{                                                                                                                                   
    return !x ? y : mindn (y % x, x) ;
}

Здравствуйте Alexander Kotelovich, Вы писали:

AK>

AK>int mindn (int x,int y)
AK>{
AK>  return !x ? y : mindn (y % x, x) ;
AK>}
AK>

(наверное, все же maxdn?)

А оценку глубины рекурсии не дадите? Скажем, на множестве аргументов (unsigned long,unsigned long)?

И если да — то какие комбинации наиболее долго раскручиваются?

int a,b,c; \\a,b — числа, причём a ДОЛЖНО быть больше b

for(;)
{
c = a%b;
if (c == 0)
break; \\НОД — b
else {
a = b;
b = c;
}
}

Писал в спешке, поэтому может что-то перепутал, поищи в Сети. Это называется "алгоритм Евклида".

Предлагаю объявить мораторий на публикацию алгоритма Евклида в любых его вариантах. Хватит уже!
(За исключением тех случаев, когда вы хотите сказать что-то принципиально новое).

Вот например, такой вопрос: оценка времени вычисления.
В частности, на каких числах НОД вычисляется дольше всего?

К>Вот например, такой вопрос: оценка времени вычисления.
К>В частности, на каких числах НОД вычисляется дольше всего?
Число шагов деления в алгоритме Евклида -- логарифмическое с
основанием равным золотому сечению. Это следует из такого
утверждения: если меньшее из чисел, для которых запущен Евклид,
меньше F_{k+1} (F_k -- числа Фибоначчи), то число шагов деления
не больше k (теорема Ламэ, кажется).