А теперь к настоящим алгоритмам, а не использованию уже написанных в стандартной библиотеке. Читаем условие задачи: Алгоритм Евклида - это, действительно, эффективный способ вычисления наибольшего общего делителя двух чисел. Но та версия, которую изучил Дима из условия задачи является неоптимальной. Давайте посмотрим на примере. Если даны два числа 1000000 и 12, то шаг 4 будет выполняться очень много раз (83333), после чего a будет равно 4, а b - 12 (затем, они, конечно, поменяются местами). На примере мы можем заметить, что 1000000 = 83333 * 12 + 4, или в общем виде a = k * b + r...

Проходят её уже в 7 классе, но помните ли Вы её ?

О статье Данная статья является вводной и надеюсь, началом серии статей по теории чисел для школьников. Цель этой вводной статьи - обратить внимание всех заинтересованных - школьников и преподавателей, на данную тему. На самом деле, зачастую и те и другие понимают, где и зачем нужна теория чисел. Например, понятно, что в ЕГЭ по математике в последнем задании могут понадобиться свойства целых чисел, которые и изучаются в теории чисел. Тем не менее, какие именно знания из этого обширного раздела могут оказаться полезны для каждого экзамена или олимпиад, для многих остается загадкой...

Приветствую Вас, уважаемые Читатели! В школе тот факт, что разложение на простые множители натуральных чисел единственно, не подвергался сомнениям. Действительно, пробуем ли мы разложить числа 56, 205 или какое-либо другое, вычисления в какой-то момент остановятся: Формализует эти вычисления основная теорема арифметики, которую доказал Евклид: Однако в математике существуют числовые системы, в которых всё не так привычно. Вспомните целые гауссовы числа: их мы произвольно определяли как: Мы же рассмотрим...