Математический форум Math Help Planet
http://mathhelpplanet.com/

Как найти общий делитель 2 чисел?
http://mathhelpplanet.com/viewtopic.php?f=10&t=29784
Страница 1 из 1

Автор:  medifh [ 01 янв 2014, 18:08 ]
Заголовок сообщения:  Как найти общий делитель 2 чисел?

Числа могут быть очень велики, но состоят из единиц. Например 11111111111111111111 и 111111111111111111111111111111111111111. Нужно найти наибольший общий делитель. Подскажите пожалуйста, хотя бы идею.

Автор:  dobby [ 01 янв 2014, 18:21 ]
Заголовок сообщения:  Re: Как найти общий делитель 2 чисел?

medifh а чем алгоритм Евклида не устраивает? :)

Автор:  medifh [ 01 янв 2014, 18:59 ]
Заголовок сообщения:  Re: Как найти общий делитель 2 чисел?

dobby писал(а):
medifh а чем алгоритм Евклида не устраивает? :)

Спасибо, не знал про такое. А если числа оооочень большие. Известно что одно из 10^8 единиц состоит, а другое из 10^16 единиц например. Как быть? Может если числа состоят из одной цифры можно через количество разрядов определить?

Автор:  andrei [ 01 янв 2014, 19:08 ]
Заголовок сообщения:  Re: Как найти общий делитель 2 чисел?

[math]\frac{ 10^{n}-1 }{ 9 }[/math] Так можно представить число,состоящее из [math]n[/math] единиц.

Автор:  dobby [ 01 янв 2014, 19:11 ]
Заголовок сообщения:  Re: Как найти общий делитель 2 чисел?

Цитата:
Может если числа состоят из одной цифры можно через количество разрядов определить?

medifh не могу сказать.
Есть такое утверждение: пусть [math]r_{n} - n[/math]-значное число [math]11 ... 1.[/math] Тогда: [math](r_{n},r_{m} )=r_{(n,m)}.[/math]
Для частных случаев очень эффективно. :)

Автор:  medifh [ 01 янв 2014, 19:48 ]
Заголовок сообщения:  Re: Как найти общий делитель 2 чисел?

Хм, а как мне разделить (10^n-1)/9 на (10^m-1)/9

Автор:  Avgust [ 01 янв 2014, 20:01 ]
Заголовок сообщения:  Re: Как найти общий делитель 2 чисел?

Разделить [math]\frac{ 10^{13}-1 }{ 9 }[/math] на [math]\frac{ 10^{18}-1 }{ 9 }[/math]

http://www.wolframalpha.com/input/?i=%2 ... %5E18-1%29

Разделить [math]\frac{ 10^{14}-1 }{ 9 }[/math] на [math]\frac{ 10^{18}-1 }{ 9 }[/math]

http://www.wolframalpha.com/input/?i=%2 ... %5E18-1%29

Автор:  Sonic [ 03 янв 2014, 11:36 ]
Заголовок сообщения:  Re: Как найти общий делитель 2 чисел?

medifh писал(а):
Хм, а как мне разделить (10^n-1)/9 на (10^m-1)/9
Вы шутите? Выпишите частное в виде дроби и сокращайте себе наздоровье. :)

Страница 1 из 1 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/