Метод пробных делений
Метод пробных делений

Алгоритм А (Разложение на простые множители путем деления). По данному положительному целому числу N этот алгоритм (рис. 1) находит простые множи­тели p1p2 ≤ … ≤pt, числа N в соответствии с равенством (1). В этом методе используется вспомогательная последовательность пробных делителей

2 = d0 < d1 < d2 < d3 … ,

которая включает в себя все простые числа (и, если это удобно, может сдержать числа, не являющиеся простыми). Последовательность чисел di должна также содержать по крайней мере одно значение, такое, что .

А1. [Начальная установка.] Присвоить t ← 0, k ← 0, nN. (В ходе выполнения алгоритма переменные t, k, n подчинены следующим условиям: "n = N/p1pt и n не имеет простых множителей, меньших dk”.)

А2. [n = 1?] Если n = 1, алгоритм заканчивается.

АЗ. [Разделить.] Присвоить q ← [n/dk], r n mod dk. (Здесь q и n — соответствен­но частное и остаток от деления числа n на dk.)

А4. [Остаток равен нулю?] Если r 0, то перейти к шагу А6,

А5. [Множитель найден.] Увеличить t на 1 и присвоить ptdk, nq. Возвра­титься к шагу А2.

А6. [Частное мало?] Если q > dk, увеличить k на 1 и возвратиться к шагу АЗ.

А7. [n — простое число.] Увеличить t на 1, присвоить ptn и завершить выполне­ние алгоритма.











Просмотров: 105 | Добавлено: 10.03.2015, 03:38
Скачать бесплатно » Математика


|