Наименьший общий делитель

Mebius · Сообщение **Mebius** » 19 янв 2011, 10:15

Здравствуйте. Как найти наименьший общий делитель для n-го ряда чисел. Например для чисел 1,2,3,4,5,6 наименьший делитель - 60.
Спасибо.

Troll1984 · Сообщение **Troll1984** » 19 янв 2011, 10:18

Наименьший общий делитель всегда равен 1
Для чисел 1, 2, 3, 4, 5, 6 он равен 1, a не 60.
60 - это наименьшее общее кратное.
Находим HOK для 1, 2, потом для полученного числа и 3, и так далее.

vicvolf · Сообщение **vicvolf** » 19 янв 2011, 10:31

Правило нахождения HOK для двух натуральных чисел смотри здесь [url=http://ru.wikipedia.org/wiki/%D0%9D%D0%B0%...%BD%D0%BE%D0%B5]http://ru.wikipedia.org/wiki/%D0%9D%D0%B0%...%BD%D0%BE%D0%B5[/url]
Если кратко, то разложение HOK содержит все простые множители, входящие хотя бы в одно из разложений чисел a, b, причём из двух показателей степени этого множителя берётся наибольший.

Mebius · Сообщение **Mebius** » 19 янв 2011, 11:15

Спасибо, алгоритм понял. Выше имел ввиду не делитель, a делимое, в данном случае кратное.

Ian · Сообщение **Ian** » 19 янв 2011, 11:42

$HOK(1,2,..n)=\Pi p^{[log_pn]$ произведение берется по всем простым числам р по порядку, перемножать можно заканчивать для p>n, все следующие сомножители равны 1

yourdomain.com