Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Факторизация!!!!!!(разложение на множители)

2.0K
04 февраля 2003 года
Invisible
26 / / 22.01.2003
Народ кто знает какой самый лучший алгоритм факторизации(разложения на множители). Кто может набросать на VB:eek:
2.0K
05 февраля 2003 года
Polev
33 / / 20.12.2002
Цитата:
Originally posted by Invisible
Народ кто знает какой самый лучший алгоритм факторизации(разложения на множители). Кто может набросать на VB:eek:


Мне так кажется что алгоритм следующий...

Делим число на delit=2. Если нацело, то запоминаем эту двойку. Механизм можно использовать разный, даже строковый.
Повторяем операцию пока нацело не делится.
Потом delit=delit+1
и так далее...
Пока результат деления не станет 1.
Получим строку типа "2*4;3*2;5*1"

Не самый оптимальный вариант, но иначе придется иметь таблицу простых чисел. Или какой-то чисто математический вариант, который мне на данный момент неизвестен.

2.0K
05 февраля 2003 года
Invisible
26 / / 22.01.2003
Цитата:
Originally posted by Polev

Не самый оптимальный вариант, но иначе придется иметь таблицу простых чисел. Или какой-то чисто математический вариант, который мне на данный момент неизвестен.


А допустим есть таблица простых чисел. Как здесь лучше сделать из файла читать по числу или загнать все простые числа в массив?

2.0K
05 февраля 2003 года
Polev
33 / / 20.12.2002
Цитата:
Originally posted by Invisible

А допустим есть таблица простых чисел. Как здесь лучше сделать из файла читать по числу или загнать все простые числа в массив?



По мне так лучше в таблицу....

267
05 февраля 2003 года
Cutty Sark
1.2K / / 17.10.2002
Вообще все зависит от конкретики.
Если тебе надо разложить 1 конкретное число на множители, то проще всего перебором.

Только delit=delit+1 лучше замени на delit=delit+2
по нечетным числам (двойку проверишь отдельно в начале). Перебирать достаточно до корня из n.
2.0K
05 февраля 2003 года
Polev
33 / / 20.12.2002
Цитата:
Originally posted by Cutty Sark

Только delit=delit+1 лучше замени на delit=delit+2
по нечетным числам (двойку проверишь отдельно в начале). Перебирать достаточно до корня из n.


Однозначно!

2.1K
05 февраля 2003 года
alexsid
18 / / 31.01.2003
Наверное, того что есть на http://algolist.manual.ru/maths/teornum/factor/ хватит с головой...

А вообще, по-моему, как раз простой перебор в произвольном случае плохо применим. Простые числа довольну круто разбегаются при увеличении, что приведет к тому что при простом переборе слишком много будет проделано операций деления впустую.

(А ведь это самая долгая операция, насколько я знаю! Нет?)

Наверное, лучше в массив их подгрузить, причем, как было указано выше, до sqr(n).
267
05 февраля 2003 года
Cutty Sark
1.2K / / 17.10.2002
Цитата:
Originally posted by alexsid
Наверное, того что есть на http://algolist.manual.ru/maths/teornum/factor/ хватит с головой...

А вообще, по-моему, как раз простой перебор в произвольном случае плохо применим. Простые числа довольну круто разбегаются при увеличении, что приведет к тому что при простом переборе слишком много будет проделано операций деления впустую.

(А ведь это самая долгая операция, насколько я знаю! Нет?)

Наверное, лучше в массив их подгрузить, причем, как было указано выше, до sqr(n).



А у тебя есть готовая таблица простых чисел?
Какого размера число ты хочешь разложить на множители?
Помни, что определять простоту числа гораздо проще, чем его раскладывать на множители.

2.0K
05 февраля 2003 года
Invisible
26 / / 22.01.2003
Цитата:
Originally posted by Cutty Sark


А у тебя есть готовая таблица простых чисел?
Какого размера число ты хочешь разложить на множители?


У меня есть таблица простых чисел до 200000. А числа которые надо раскладывать от 600 знаков.

267
05 февраля 2003 года
Cutty Sark
1.2K / / 17.10.2002
Цитата:
Originally posted by Invisible

У меня есть таблица простых чисел до 200000. А числа которые надо раскладывать от 600 знаков.



Криптографией увлекаешься... Флаг в руки... :)

2.0K
05 февраля 2003 года
Invisible
26 / / 22.01.2003
Цитата:
Originally posted by alexsid
Наверное, того что есть на http://algolist.manual.ru/maths/teornum/factor/ хватит с головой...


С головой хватит если английский знаешь. А русские ресурсы есть по поводу.

2.1K
06 февраля 2003 года
alexsid
18 / / 31.01.2003
Цитата:
Originally posted by Invisible

У меня есть таблица простых чисел до 200000. А числа которые надо раскладывать от 600 знаков.


Таблица простых чисел, на мой взгляд, вообще не проблема. Какое-нибудь "Решето Эратосфена" или на крайний случай какой-нибудь МатКАД... Таблицу можно составить.

А числа твои сверху как-нибудь ограничены?

На счет русских ресурсов не знаю. Может где-нибудь там же, на algolist.manual.ru?

2.0K
06 февраля 2003 года
Invisible
26 / / 22.01.2003
Цитата:
Originally posted by alexsid

А числа твои сверху как-нибудь ограничены?


Ну я же говорю, верхний предел 200000

Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог