Покинул форум
Сообщений всего: 52
Дата рег-ции: Янв. 2012 Откуда: Омск, Россия
Помог: 0 раз(а)
Здравствуйте.
есть некоторое число N. нужно разложить его на множители и вывести два, сумма которых наименьшая.
Например, N = 24
Раскладываем на множители:
24 = 2*2*2*3 (простые числа)
из этих чисел можно составить пары, произведение которых будет равно 24:
2 и 12 (2 и 2*2*3)
4 и 6 (2*2 и 2*3)
8 и 3 (2*2*2 и 3)
2+12 = 14
4+6=10
8+3=11
Наименьшая сумма равна 10, следовательно нужно вывести два числа: 4 и 6
Как реализовать такое?
не хотелось бы лепить кучу циклов в коде... (решето Эратосфена, чтобы разложить на множители, само разложение, перебор чисел, составление пар...)
Заранее благодарен
EuGen
Отправлено: 07 Февраля, 2013 - 18:34:30
Профессионал
Покинул форум
Сообщений всего: 9095
Дата рег-ции: Июнь 2007 Откуда: Berlin
Помог: 707 раз(а)
Если не хочется возиться с большим числом циклов, то Вы, безусловно, можете воспользоваться, к примеру, методом эллиптических кривых или методом общего решета числового поля. Правда их реализация много сложнее решета Эратосфена. И вообще факторизация числа - это NP-полная задача (на текущий момент).
Что же до составления пар- этого и не потребуется. В силу верности утверждения
min(Xi)+min(Yj)<=min(Xi+Yj), x,y>=0, i,j in {N}
- достаточно получить список множителей в отсортированном виде (можете воспользоваться, например, sort) и искомая сумма будет суммой первых двух элементов.
----- Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
Champion
Отправлено: 07 Февраля, 2013 - 22:14:23
Активный участник
Покинул форум
Сообщений всего: 4350
Дата рег-ции: Авг. 2008 Откуда: Москва
Помог: 57 раз(а)
EuGen пишет:
и искомая сумма будет суммой первых двух элементов.
Ну не совсем. В этом примере два первых элемента будет 2 и 3, но они пару не образуют. Лучше все-таки искать минимум в суммах.
(Добавление)
Но можно разложить и исходное число, и 24 таким способом, а потом, действительно брать по очереди множители исходного числа, если такой же множитель есть и у 24, то отложить его в кучку и убрать из рассмотрения из 24 (только учесть, что и у 24, и у самого исходного числа может быть по несколько одинаковых множителей). Получившаяся последовательность будет состоять из минимальных множителей, которые дадут 24.
Теперь можно циклом, перебрав половину этих множителей получать два числа
div24 и 24/div24 (div24 - это перемноженный на все предыдущие множитель из полученных на предыдущем этапе), найти сумму и сравнить ее с минимальной
EuGen
Отправлено: 07 Февраля, 2013 - 22:29:36
Профессионал
Покинул форум
Сообщений всего: 9095
Дата рег-ции: Июнь 2007 Откуда: Berlin
Помог: 707 раз(а)
Хотя да, я не досмотрел, что нужна именно полная пара, а не просто пара множителей. В таком случае минимальную сумму дадут те, что наиболее близки к квадратному корню от числа. Иными словами - у нас есть множество делителей, выбираем из них тот, что наиболее близок к квадратному корню и затем делим исходное число на него, получая второй множитель. Итог - оба найдены, перебор не нужен.
Champion пишет:
А по поводу разложения, такое не покатит?
Вполне, но этот метод и есть - суть полный перебор. То же решето Эратосфена даст более быстрый результат.
----- Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
Champion
Отправлено: 07 Февраля, 2013 - 22:40:39
Активный участник
Покинул форум
Сообщений всего: 4350
Дата рег-ции: Авг. 2008 Откуда: Москва
Помог: 57 раз(а)
Но этот перебор остановится, когда делить ни на что не останется.
А решето Эратосфена подразумевается использовать для получения N простых чисел? Нам же все равно сначала надо проинициализировать массив-решето числами в кличестве N (или N-1, не помню).
Хотя, конечно, инициализация решета менее затратна, чем иф с делением, но большинство раз, я думаю, этот цикл будет заканчиваться числа так до 53. Но с большими простыми множителями будет конечно медленноват
EuGen
Отправлено: 07 Февраля, 2013 - 22:45:08
Профессионал
Покинул форум
Сообщений всего: 9095
Дата рег-ции: Июнь 2007 Откуда: Berlin
Помог: 707 раз(а)
Champion пишет:
Но этот перебор остановится, когда делить ни на что не останется.
- так любой перебор должен останавливаться. Кстати, перебирать достаточно до округленного вверх квадратного корня из исходного числа.
Я планирую сделать факторизацию по методу эллиптических кривых. К слову сказать, это на данный момент вообще единственный метод, отличный от перебора, который позволяет факторизовать число с произвольными множителями. Но даже он имеет оценочную сложность \exp(\sqrt{2}/2 + o(1) \sqrt{p \ln p \ln (\ln p)}) , где p - наименьшие делитель исходного числа. Вообще эта задача пока что NP-полна, и именно на этом факте зиждется современная криптография. Если удастся найти полиномиальный способ факторизации, то все шифрование (как, например, RSA) пойдет прахом.
----- Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
Champion
Отправлено: 07 Февраля, 2013 - 22:46:13
Активный участник
Покинул форум
Сообщений всего: 4350
Дата рег-ции: Авг. 2008 Откуда: Москва
Помог: 57 раз(а)
EuGen пишет:
Иными словами - у нас есть множество делителей, выбираем из них тот, что наиболее близок к квадратному корню и затем делим исходное число на него
Опять же в примере числа 4 и 6 - изначально у нас их нет. Они сами получаются перемножением наших имеющихся делителей.
Кстати, наверное, вообще правильнее разлагать только 24, получать пары, а потом искать пары в большом числе в порядке их сумм (Добавление)
EuGen пишет:
Я планирую сделать факторизацию по методу эллиптических кривых
Он, к сожаленнию, выходит за границы моих математических познаний, поэтому я не могу оценить, на сколько этот метод крут)
EuGen пишет:
так любой перебор должен останавливаться.
Ну разумеется) Я просто предположил, что это произойдет быстрее, чем перебор до N (я почему-то только о нем подумал).
EuGen пишет:
Кстати, перебирать достаточно до округленного вверх квадратного корня из исходного числа.
Точно.
EuGen
Отправлено: 07 Февраля, 2013 - 22:48:07
Профессионал
Покинул форум
Сообщений всего: 9095
Дата рег-ции: Июнь 2007 Откуда: Berlin
Помог: 707 раз(а)
Champion пишет:
Опять же в примере числа 4 и 6 - изначально у нас их нет. Они сами получаются перемножением наших имеющихся делителей.
Ну так я же и сказал - что нужны все множители. Я не писал, что это разложение должно быть в канонической форме (то есть в виде степеней простых чисел). Если они у нас есть, то алгоритм поиска я уже указал, перебор там не нужен. Перебор же чисел при факторизации - в любом случае неизбежен (можно лишь "оптимизировать затраты").
Champion пишет:
Он, к сожаленнию, выходит за границы моих математических познаний, поэтому я не могу оценить, на сколько это круто)
Все гости форума могут просматривать этот раздел. Только зарегистрированные пользователи могут создавать новые темы в этом разделе. Только зарегистрированные пользователи могут отвечать на сообщения в этом разделе.