Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Алгоритм разбит на три части:
08.06.04 13:58 Число просмотров: 4698
Автор: volizar Статус: Незарегистрированный пользователь
|
Алгоритм разбит на три части:
1. Факторизация
2. Корень, т.е. «хвост»
3. Вставка (новое)
1.Факторизация
Возьмем число А. Извлечем корень а. Из таблицы простых чисел берем число b, ближайшее к а, так что b <= a. Делим А на b. Имеем b , c (второе целое число) и d (остаток. Если d равен нулю, то факторизация завершена). A = b*c +d.
Если d будет больше b, d >b , то надо проделать еще кое-что.
А именно: находим новое c, c:= c + d/b (без остатка)
новое d, d:= d (mod b)
Пока у нас есть b, c и d. Наша задача – довести d до нуля.
Процедура такая:
Берём следующее простое число b2, так что b2<b1.
Ищем следующее d. Оно будет равно d: = d + (c - b2)*( b1 - b2).
Само c станет равно c: = c + (b1 - b2).
Если d будет больше b2, d >b2 , то
находим новое c, c = c + d/b2 (без остатка)
новое d, d = d (mod b2)
В принципе, это вся первая часть. Пример:
A = 377, a = 19.146…, b = 19, c = 19, d = 16
Шаг 1 : b2 = 17, d = 16 + (19 - 17)*(19-17) = 20, c = 19 + 2 = 21.
Видим d >b2, находим c = 21 + d/b = 21 +1 = 22
d = 20(mod17) = 3
Шаг 2: b = 13, d = 3 + ( 22 - 13)*(17-13) = 39, c = 22 + 4 = 26.
Опять d > b, значит c = 26 + 3 = 29, d = 39(mod13) = 0.
Процедура закончена. Результат: b = 13, c = 29.
На мой взгляд, алгоритм сам по себе очень удобный и не потребует много ресурсов.
Но это всего лишь один механизм обработки данных.
Осталось ещё два. Но об этом позже.
P.S. Есть пока замечания? Не придирайтесь, пожалуйста к мелочам.
|
|
|