Факторизация!!!!!!(разложение на множители)
Народ кто знает какой самый лучший алгоритм факторизации(разложения на множители). Кто может набросать на VB:eek:
Мне так кажется что алгоритм следующий...
Делим число на delit=2. Если нацело, то запоминаем эту двойку. Механизм можно использовать разный, даже строковый.
Повторяем операцию пока нацело не делится.
Потом delit=delit+1
и так далее...
Пока результат деления не станет 1.
Получим строку типа "2*4;3*2;5*1"
Не самый оптимальный вариант, но иначе придется иметь таблицу простых чисел. Или какой-то чисто математический вариант, который мне на данный момент неизвестен.
Не самый оптимальный вариант, но иначе придется иметь таблицу простых чисел. Или какой-то чисто математический вариант, который мне на данный момент неизвестен.
А допустим есть таблица простых чисел. Как здесь лучше сделать из файла читать по числу или загнать все простые числа в массив?
А допустим есть таблица простых чисел. Как здесь лучше сделать из файла читать по числу или загнать все простые числа в массив?
По мне так лучше в таблицу....
Если тебе надо разложить 1 конкретное число на множители, то проще всего перебором.
Только delit=delit+1 лучше замени на delit=delit+2
по нечетным числам (двойку проверишь отдельно в начале). Перебирать достаточно до корня из n.
Только delit=delit+1 лучше замени на delit=delit+2
по нечетным числам (двойку проверишь отдельно в начале). Перебирать достаточно до корня из n.
Однозначно!
А вообще, по-моему, как раз простой перебор в произвольном случае плохо применим. Простые числа довольну круто разбегаются при увеличении, что приведет к тому что при простом переборе слишком много будет проделано операций деления впустую.
(А ведь это самая долгая операция, насколько я знаю! Нет?)
Наверное, лучше в массив их подгрузить, причем, как было указано выше, до sqr(n).
Наверное, того что есть на http://algolist.manual.ru/maths/teornum/factor/ хватит с головой...
А вообще, по-моему, как раз простой перебор в произвольном случае плохо применим. Простые числа довольну круто разбегаются при увеличении, что приведет к тому что при простом переборе слишком много будет проделано операций деления впустую.
(А ведь это самая долгая операция, насколько я знаю! Нет?)
Наверное, лучше в массив их подгрузить, причем, как было указано выше, до sqr(n).
А у тебя есть готовая таблица простых чисел?
Какого размера число ты хочешь разложить на множители?
Помни, что определять простоту числа гораздо проще, чем его раскладывать на множители.
А у тебя есть готовая таблица простых чисел?
Какого размера число ты хочешь разложить на множители?
У меня есть таблица простых чисел до 200000. А числа которые надо раскладывать от 600 знаков.
У меня есть таблица простых чисел до 200000. А числа которые надо раскладывать от 600 знаков.
Криптографией увлекаешься... Флаг в руки... :)
Наверное, того что есть на http://algolist.manual.ru/maths/teornum/factor/ хватит с головой...
С головой хватит если английский знаешь. А русские ресурсы есть по поводу.
У меня есть таблица простых чисел до 200000. А числа которые надо раскладывать от 600 знаков.
Таблица простых чисел, на мой взгляд, вообще не проблема. Какое-нибудь "Решето Эратосфена" или на крайний случай какой-нибудь МатКАД... Таблицу можно составить.
А числа твои сверху как-нибудь ограничены?
На счет русских ресурсов не знаю. Может где-нибудь там же, на algolist.manual.ru?
А числа твои сверху как-нибудь ограничены?
Ну я же говорю, верхний предел 200000