Книги-online

Теория чисел.

И в библиотеке бывают рекламные паузы.

Теория чисел.

Наибольший общий делитель двух целых чисел (алгоритм Евклида).

Наибольшим общим делителем (НОД) двух целых чисел называется такое наибольшее по модулю число, которое делит эти два числа. По определению НОД(0,0)=0.

Данный алгоритм вычисления НОД двух целых чисел a и b состоит в следующем: если хотя бы одно из чисел равно нулю, то НОД(a,b)=|a+b|, в других случаях последовательно находятся остатки ri от делений:

	a на b-a=bq1+r1,
	b на r1-b=r1q2+r2,
	r1 на r2-r1=r2q3+r3,
	. . . . . .

и т.д., пока rn+1 не станет равно нулю. Тогда НОД(a,b)=НОД(b,r1)=НОД(r1 ,r2)=...=НОД(rn-1 ,rn )=rn. Наверх

Наибольший общий делитель двух целых чисел (бинарный алгоритм Евклида).

Данный алгоритм вычисления НОД(a,b) основан на бинарном алгоритме Евклида. Вычисления проводятся на основании следующих свойств НОД:

	НОД(2m,2n)=2 НОД(m,n),
	НОД(2m,2n+1)= НОД(m,2n+1),
	НОД(-m,n)= НОД(m,n).

Наверх

Наибольший общий делитель двух целых чисел (расширенный алгоритм Евклида).

Алгоритм, кроме поиска НОД двух целых чисел a,b также находит величины x,y, т.ч. ax+by=НОД(a,b). Алгоритм включает в себя алгоритм Евклида и похож на алгоритм решения диофантового уравнения, который рассматривается здесь. Привожу его поскольку часто возникает необходимость отыскать именно x,y удовлетворяющие приведенному выше условию. Наверх

Наименьшее общие кратное двух целых чисел.

Наименьшим общим кратным двух целых чисел a и b называется наименьшее положительное число, которое делится на a и b.

Известно, что

	НОК(a,b)=ab/НОД(a,b).

Сначала в функцие вычисляется НОД(a,b), затем НОК по предыдущей формуле. При a=0 или b=0 НОК полагается равным 0. Наверх

Решето Эратосфена для нахождения простых чисел.

В последовательности чисел 2,3, ... , n последовательно вычеркиваем каждое второе число после 2. Первое незачеркнутое число простое (3). Далее вычеркиваем каждое третье число после 3. Первое незачеркнутое число простое (5). Затем вычеркиваем каждое пятое число после 5 и т.д. до тех пор, пока не дойдем до числа, большего корня из n (известно, что если целое положительное число n неравное 1 не делится ни на одно положительное простое число, не большее корня из n то оно простое). Все числа, которые остаются, простые. Такой метод нахождения простых чисел называется решетом Эратосфена.

Колличество простых чисел r не превышает:

	trunc(1.6n/ln n+1), если n200.

Процедура заполняет массив P простыми числами меньшими n, элемент массива является последним, если следующий за ним элемент равен 0. Наверх

Сложение двух целых положительных чисел в системе с основанием p.

Алгоритм складывает два целых числа A и B представленных в системе счисления с основанием p. Цифры p-ичного разложения чисел хранятся в массивах a и b при этом число A имеет n разрядов, а число B - m.

	A=anpn+an-1pn-1+...+a0,
	B=bmpm+bm-1pm-1+...+b0.

Элементы массивов - целые в промежутке от 0 до p-1. Сумма помещается в массив C, а колличество разрядов суммы представленно переменной l.

Алгоритм достаточно простой и приводится только потому, что в дальнейшем я буду его использовать. Всю информацию об алгоритме можно получить из блок-схемы. Наверх

Сравнение двух целых положительных чисел в системе с основанием p.

Алгоритм сравнивает два целых числа A и B представленных в системе счисления с основанием p. Цифры p-ичного разложения чисел хранятся в массивах a и b при этом число A имеет n разрядов, а число B - m.

	A=anpn+an-1pn-1+...+a0,
	B=bmpm+bm-1pm-1+...+b0.

Элементы массивов - целые в промежутке от 0 до p-1. Результат работы функции -1,0,1 соответствует случаям A < B, A=B, A > B.

Разность двух целых положительных чисел в системе с основанием p.

Алгоритм вычисляет разность двух целых числа A и B представленных в системе счисления с основанием p. Цифры p-ичного разложения чисел хранятся в массивах a и b при этом число A имеет n разрядов, а число B - m.

	A=anpn+an-1pn-1+...+a0,
	B=bmpm+bm-1pm-1+...+b0.

Элементы массивов - целые в промежутке от 0 до p-1. Результат работы помещается в массив С, колличество разрядов разности представленно переменной l, знак разности совпадает с знаком sign.

Всю информацию об алгоритме можно получить из блок-схемы.Используется описанный ранее алгоритм сравнения. Наверх

Произведение двух целых положительных чисел в системе с основанием p.

Алгоритм вычисляет произведение двух целых числа A и B представленных в системе счисления с основанием p. Цифры p-ичного разложения чисел хранятся в массивах a и b при этом число A имеет n разрядов, а число B - m.

	A=anpn+an-1pn-1+...+a0,
	B=bmpm+bm-1pm-1+...+b0.

Элементы массивов - целые в промежутке от 0 до p-1. Результат работы помещается в массив С, колличество разрядов произведения представленно переменной l.

Всю информацию об алгоритме можно получить из блок-схемы. Наверх

Частное и остаток при делении двух целых положительных чисел в системе счисления с основанием p.

Алгоритм вычисляет частное и остаток при делении двух целых числа A и B представленных в системе счисления с основанием p. Цифры p-ичного разложения чисел хранятся в массивах a и b при этом число A имеет n разрядов, а число B - m.

	A=anpn+an-1pn-1+...+a0,
	B=bmpm+bm-1pm-1+...+b0.

Элементы массивов - целые в промежутке от 0 до p-1. Частное помещается в массив С, колличество разрядов частного представленно переменной l. Остаток помещается в массив D, колличество разрядов остатка представленно переменной k.

Всю информацию об алгоритме можно получить из блок-схемы. Используются описанные ранее алгоритмы вычитания и сравнения. Наверх

Перевод числа из системы счисления с основанием p в систему счисления с основанием q.

Алгоритм переводит число представленное в системе счисления с основанием p в систему счисления с основанием q. Цифры p-ичного разложения числа хранятся в массиве a при этом число в этой системе имеет n разрядов. Полученное представление в системе с основанием q помещается в массив b и имеет m разрядов:

	A=anpn+an-1pn-1+...+a0=bmqm+bm-1qm-1+...+b0.

Элементы массива a - целые в промежутке от 0 до p-1, элементы массива b - целые в промежутке от 0 до q-1. В зависимости от того основание какой системы счисления больше, применяется разные алгоритмы перевода:

1. В случае p > q алгоритм перевода заключается в последовательном делении исходного числа на q (операция осуществляется в системе с основанием p) и заполнения массива b остатками от деления (заполнять начинаем с младшего разряда). Т.е.

	A = A1*q+b0
	A1 = A2*q+b1
	...

Понятно, что для некоторого k получим Ak=0 и алгоритм завершится.

2. В случае p < q алгоритм перевода заключается в вычислении:

	A=an*pn+an-1*pn-1+a0

при этом операции производим в системе счисления с основанием q.

В принципе в обоих случаях можно использовать алгоритм 2, но если во-втором случае известно представление p в системе с основанием q, то в случае p > q его вначале необходимо получить. Использование алгоритма 1 в случае 2, так же не слишком привлекательно, т.к. если в случае 1, остаток всегда представляется одной цифрой, то в случае 2 такое свойство нарушается.

Полною информацию об алгоритме можно получить из блок-схемы. Используются описанные ранее алгоритмы сложения,сравнения, умножения и деления с остатком. Наверх