Простое деление

Алгоритмы


	Главная
	Понятие алгоритма
	Больше про алгоритмы
	Анализ
	Теория алгоритмов
	Основные конструкции
	Сортировка
	Математика
	Геометрия
	Комбинаторика
	Сжатие и кодирование
	Сжатие изображений
	Шифрование
	Исходники

Статьи

Что такое информация

Искусственный интеллект

Чего не может компьютер

Модемы

История архитектуры ПК

CD-ROM

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

Наиболее наивный подход - просто делить на все числа подряд до корня из N. Если Вы хотели узнать это - дальше можно не читать ;-)

     Пусть мы хотим поделить N на все простые числа до корня из N. Для этого мы можем иметь или не иметь в своем распоряжении достаточно большую таблицу простых чисел. Если это не так, то, очевидно, мы можем делить N на числа d в заданных классах эквивалентности, например, 1 и 5 по модулю 6, или 1,7,11,13,17,19,23,29 по модулю 30. Тогда мы проделаем много бессмысленных делений (на составные числа), однако результат останется верным. Таким образом, можно составить следующий алгоритм:

     Предположим, что у нас уже есть таблица простых чисел: p[1] = 2, p[2] = 3, ... , p[k], где k > 3, массив t := [6,4,2,4,2,4,6,2], и индекс j, такой что если p[k] mod 30 равно 1,7,11,13,17,19,23 или 29, то j := 0,1,2,3,4,5,6 или 7 соответственно.
     Выберем некоторую верхнюю грань B, такую что B >= p[k], чтобы не тратить на этот алгоритм слишком много времени.

     Получив на входе положительное целое число N, этот алгоритм пытается разложить его на множители, и, если это не получается, то N - число без простых делителей, меньших либо равных B.

[Инициализация]
Если N <= 5, вывести разложение 1 = 1, 2 = 2, 3 = 3, 4 = 2², 5 = 5 в зависимости от N и выйти. Иначе, i := -1, m := 0, L := [ N^1/2 ]
[Cледующее простое]
Пусть m := m + 1. Если m > k, то i : = j - 1 и идти к шагу 5, иначе d : = p[m].
[Простое деление]
Пусть r : = N mod d. Если r = 0, то вывести d как нетривиальный делитель N и выйти ( или N := N / d, L : = [ N^1/2 ] и повторить шаг 3, если мы хотим продолжить нахождение делителей N).
[Простое?]
Если d >= L, то в случае N > 1 вывести сообщение, что оставшаяся часть N - простое и выйти. Иначе, если i < 0 идти на шаг 2.
[Следующий делитель]
Пусть i := i + 1 mod 8, d := d + t[i]. Если d > B, то вывести сообщение о том, что оставшиеся простые делители N больше B, иначе идти на шаг 3.

     Заметим, что i = -1 пока мы используем нашу таблицу простых и i >= 0 если нет. Этот тест не следует использовать для полной факторизации, кроме тех случаев, когда N - очень маленькое ( например, N < 10⁸), так как для этого есть лучшие методы. Однако, с другой стороны, он весьма полезен для удаления малых множителей.
Заметки к практической реализации. Предположим, что мы используем таблицу простых до 500'000 ( 41'538 простых чисел ). Простое деление при таком ограничении никогда не занимает больше нескольких секунд на современных компьютерах. Причем хранить можно только разности между простыми (или их половины), а не сами числа, так как p[k] - p[k-1] можно поместить в 1 байт вместо четырех, если p[k] <= 1'872'851'947 ( а половину этой разности - если p[k] <= 1'999'066'711'391).

     Кроме того, не нужно делать больше делений после того, как кончится таблица простых, так как есть лучшие методы для удаления малых делителей.

     И, наконец, заметим, что нет необходимости в вычислении L := [ N^1/2 ] во время инициализации, так как проверка d >= L в шаге 4 может быть заменена на q <= L, где q - евклидово частное при делении N на d : N = q * d + r, обычно вычисляемое одновременно с остатком в шаге 3.

Бетон можно выгодно купить у нас быстро и просто, бетон цена прайс в компании "Летера". . Уборку помещений можно заказать по телефону 8(495)979-95-05, звоните.