Страница 1 из 1
Наименьший общий делитель
Добавлено: 19 янв 2011, 10:15
Mebius
Здравствуйте. Как найти наименьший общий делитель для n-го ряда чисел. Например для чисел 1,2,3,4,5,6 наименьший делитель - 60.
Спасибо.
Наименьший общий делитель
Добавлено: 19 янв 2011, 10:18
Troll1984
Наименьший общий делитель всегда равен 1
Для чисел 1, 2, 3, 4, 5, 6 он равен 1, a не 60.
60 - это наименьшее общее кратное.
Находим HOK для 1, 2, потом для полученного числа и 3, и так далее.
Наименьший общий делитель
Добавлено: 19 янв 2011, 10:31
vicvolf
Правило нахождения 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, причём из двух показателей степени этого множителя берётся наибольший.
Наименьший общий делитель
Добавлено: 19 янв 2011, 11:15
Mebius
Спасибо, алгоритм понял. Выше имел ввиду не делитель, a делимое, в данном случае кратное.
Наименьший общий делитель
Добавлено: 19 янв 2011, 11:42
Ian
![$$HOK(1,2,..n)=\Pi p^{[log_pn]$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24HOK%281%2C2%2C..n%29%3D%5CPi%20p%5E%7B%5Blog_pn%5D%24%24 "$$HOK(1,2,..n)=\Pi p^{[log_pn]$$")
произведение берется по всем простым числам р по порядку, перемножать можно заканчивать для p>n, все следующие сомножители равны 1