Алгоритм поиска множителей числа, то есть представление какого либо числа в виде двух других чисел, при умножении которых мы получил непосредственно то число, которое нам нужно. Эта статья не рассказывает о каких либо идеальных/лучших алгоритмов, это своего рода оптимизация перебора чисел, и далеко не стоит по сравнению с тем же методом факторизации Ферма ну или Ро-алгоритмом Полларда.
В чем заключается данный алгоритм?
В первую очередь, берем интервал чисел, который представляем в виде двух целых чисел, это конец интервала и его начало. Так же нам нужно число, с которого мы хотим получить множители на интервале.
Теперь перейдем к самому алгоритму. Чтобы не идти вглубь математики, мы будем рассматривать этот метод исключительно на человеческом языке.
Для начала, нам нужны сами пределы интервала, их мы пусть присвоим 'x' и 'y', начало и конец соответственно.
Теперь мы, умножаем эти два числа: z = x*y, и если число, которое мы получили, будет меньше, чем число которое мы планируем факторизовать, то прибавляем к 'x' — единицу(1), и снова умножаем: z = (x+1)*y, и так до тех пор, пока мы не получим (z > N), где 'N' — число которое нужно факторизовать.
Если же, число которое мы получили больше N, то:
1. Мы ищем разницу между 'z' и 'N', то есть между числом которое мы получили и число которое мы хотим факторизовать.
2.1. Число, которое мы получили после вычитания(q), делим на число которое символизирует начало интервала(x). После чего, проверяем условие: Если получается число, не целого типа, то множителей не будет, а следовательно мы увеличиваем начальное значение(x) на единицу и продолжаем поиск.
2.2. Если же, число которое мы получили при делении — целого типа, тогда мы: От конца интервала отнимаем число которое мы получили(пусть будет 'l'), в следствии чего мы получаем один из множителей, второй же множитель — это 'x'.
Пример:
Есть интервал чисел от 14 к 28, и число которое мы хотим разложить на множители, пусть будет 450.
Для начала нам нужно два числа, это начало и конец интервала, в данном случаи это 14 и 28. Дальше мы согласно алгоритму, эти два числа умножаем и получаем результат:
Число, которое мы получили, меньше чем число, которое нам нужно разложить на множители, то есть 450, тогда мы увеличиваем 14 на единицу, и начинаем все с начала.
Опять же, 420 < 450, тогда мы к 15 прибавляем единицу и продолжаем поиск.
По тому же принципу, 448 < 450, значит мы к 16 прибавляем единицу и двигаемся дальше.
Уже здесь мы видим, что число, которое мы получили при умножении больше чем 450, тогда мы, согласно пункту «1» ищем разницу между 476 и 450.
Теперь главная проверка вечера, согласно пункту 2.1 мы делим это число на начало интервала в надежде на то, что мы получим целое число.
К сожалению мы получили число НЕ целого типа, это значит что множителей тут нет, прибавляем к 17 единицу и продолжаем поиск.
Согласно пункту 1 ищем разницу:
Теперь главная проверка, делим полученное число на 18, получаем результат:
А вот и число целого типа, то есть уже на этом этапе понятно что множители мы нашли, теперь согласно пункту 2.2 нам нужно их точно высчитать:
Один множитель мы получили, отняв от конца интервала число которое мы посчитали.
Ну а второй множитель это конечно же сам 'x' ну или же в нашем случаи это 18.
Проверяем:
По такому принципу работает этот алгоритм, на самом деле он далеко не хороший, так как во первых при очень большом интервале поиск множителей может идти довольно долго, и вообще я без документации, без сторонней помощи вышел на него, возможно он уже и был где-то описан, но этот алгоритм можно назвать «ради идеи», ну и чтобы не деградировать.
В чем заключается данный алгоритм?
В первую очередь, берем интервал чисел, который представляем в виде двух целых чисел, это конец интервала и его начало. Так же нам нужно число, с которого мы хотим получить множители на интервале.
Теперь перейдем к самому алгоритму. Чтобы не идти вглубь математики, мы будем рассматривать этот метод исключительно на человеческом языке.
Для начала, нам нужны сами пределы интервала, их мы пусть присвоим 'x' и 'y', начало и конец соответственно.
x = start,
y = end;Теперь мы, умножаем эти два числа: z = x*y, и если число, которое мы получили, будет меньше, чем число которое мы планируем факторизовать, то прибавляем к 'x' — единицу(1), и снова умножаем: z = (x+1)*y, и так до тех пор, пока мы не получим (z > N), где 'N' — число которое нужно факторизовать.
Если же, число которое мы получили больше N, то:
1. Мы ищем разницу между 'z' и 'N', то есть между числом которое мы получили и число которое мы хотим факторизовать.
z - N = q;2.1. Число, которое мы получили после вычитания(q), делим на число которое символизирует начало интервала(x). После чего, проверяем условие: Если получается число, не целого типа, то множителей не будет, а следовательно мы увеличиваем начальное значение(x) на единицу и продолжаем поиск.
q/x = if(int) => Пункт 2.2
else if(double) => x += 1.2.2. Если же, число которое мы получили при делении — целого типа, тогда мы: От конца интервала отнимаем число которое мы получили(пусть будет 'l'), в следствии чего мы получаем один из множителей, второй же множитель — это 'x'.
y - l = a,
a * x = N;Пример:
Есть интервал чисел от 14 к 28, и число которое мы хотим разложить на множители, пусть будет 450.
Для начала нам нужно два числа, это начало и конец интервала, в данном случаи это 14 и 28. Дальше мы согласно алгоритму, эти два числа умножаем и получаем результат:
14*28 = 392 Число, которое мы получили, меньше чем число, которое нам нужно разложить на множители, то есть 450, тогда мы увеличиваем 14 на единицу, и начинаем все с начала.
15*28 = 420Опять же, 420 < 450, тогда мы к 15 прибавляем единицу и продолжаем поиск.
16*28 = 448По тому же принципу, 448 < 450, значит мы к 16 прибавляем единицу и двигаемся дальше.
17*28 = 476Уже здесь мы видим, что число, которое мы получили при умножении больше чем 450, тогда мы, согласно пункту «1» ищем разницу между 476 и 450.
476-450 = 26Теперь главная проверка вечера, согласно пункту 2.1 мы делим это число на начало интервала в надежде на то, что мы получим целое число.
26/17 = ~ 1.53К сожалению мы получили число НЕ целого типа, это значит что множителей тут нет, прибавляем к 17 единицу и продолжаем поиск.
18*28 = 504Согласно пункту 1 ищем разницу:
504-450 = 54Теперь главная проверка, делим полученное число на 18, получаем результат:
54/18 = 3А вот и число целого типа, то есть уже на этом этапе понятно что множители мы нашли, теперь согласно пункту 2.2 нам нужно их точно высчитать:
28-3 = 25Один множитель мы получили, отняв от конца интервала число которое мы посчитали.
Ну а второй множитель это конечно же сам 'x' ну или же в нашем случаи это 18.
Проверяем:
25 * 18 = 450, Отлично! И самое главное что эти числа входят в наш интервал.По такому принципу работает этот алгоритм, на самом деле он далеко не хороший, так как во первых при очень большом интервале поиск множителей может идти довольно долго, и вообще я без документации, без сторонней помощи вышел на него, возможно он уже и был где-то описан, но этот алгоритм можно назвать «ради идеи», ну и чтобы не деградировать.
Of course, winning is one of the main goals, but we must remember that there is no ideal, and if you think that you have achieved this ideal — you have lost.