Сайт о программировании, математике и моделировании
Записи с метками наибольший общий делитель
Нахождение наибольшего общего делителя двух натуральных чисел
3 Декабрь
Постановка задачи:
Найти наибольший общий делитель (НОД) двух введенных натуральных чисел, используя алгоритм Евклида (алгоритм Евклида: вычитаем из большего меньшее до тех пор, пока они не сравняются, полученное в результате число и есть НОД).
Решение:
Наибольшим общим делителем (НОД) двух целых чисел называется такое наибольшее по модулю число, которое делит эти два числа. Так как натуральные числа это положительные целые числа, то при вводе двух чисел а и b должно проверяться условие, что они больше нуля. Читать дальше >
Ускорение РО-алгоритма с помощью алгоритма нахождения периода последовательности методом Брента.
1 Декабрь
1. [Начальная установка.] Присвоить x←5, x’←2, k←1, l←1, n←N. (Во время выполнения этого алгоритма число n не является множителем числа N, а переменные x и x’ представляют величины xm mod n xl(m)-1 mod n в выражении (1), где также f(x)=x2+1, A=2, l=l(m) и k=2l-m.)
2.1. [Проверить, будет ли число простым.] Если n – простое число Читать дальше >
Методы ускорения алгоритмов
1 Декабрь
Первый метод ускорения заключается в том, что время вычисления НОД занимает много времени, поэтому используем китайскую теорему об остатках и попробуем ускорить начальный алгоритм. Китайская теорема об остатках: любое не отрицательное число которое не превышает каждого из множителей модуля можно однозначно восстановить если известны его остатки по этим модулям. Читать дальше >
Теория чисел
1 Декабрь
Числа 1,2,3,… называются натуральными. Число 0, а также числа вида ±a, где a натуральное число, называются целыми числами. Отношение двух целых чисел называется рациональной дробью и является формальной записью результата деления одного числа на другое. Деление на ноль не определено. Простым числом называется натуральное число, у которого есть в точности два неравных натуральных делителя. Наибольшим общим делителем двух целых чисел a и b называется наибольшее целое число, которое делит как a, так и b. Обозначения: (a,b) или НОД(a,b). Читать дальше >
