Прежде, чем перейти к более сложным материям, рассмотрим самый простой, наивный метод простого деления. И в самом деле, практически при любом алгоритме факторизации оптимально использовать этот способ до некоторой границы 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 = 22, 5 = 5 в зависимости от N и выйти. Иначе, i := -1, m := 0, L := [ N1/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 : = [ N1/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 < 108), так как для этого есть лучшие методы.
Однако, с другой стороны, он весьма полезен для удаления малых множителей.
Заметки к практической реализации.
Предположим, что мы используем таблицу простых до 500'000 ( 41'538 простых чисел ). Простое деление при таком ограничении никогда не занимает больше нескольких секунд на современных компьютерах. Причем хранить можно только разности между простыми (или их половины), а не сами числа, так как p[k] - p[k-1] можно поместить в 1 байт вместо четырех, если p[k] <= 1'872'851'947 ( а половину этой разности - если p[k] <= 1'999'066'711'391).
Кроме того, не нужно делать больше делений после того, как кончится таблица простых, так как есть лучшие методы для удаления малых делителей.
И, наконец, заметим, что нет необходимости в вычислении L := [ N1/2 ] во время инициализации, так как проверка d >= L в шаге 4 может быть заменена на q <= L, где q - евклидово частное при делении N на d : N = q * d + r, обычно вычисляемое одновременно с остатком в шаге 3.
