Здравствуйте.
есть некоторое число 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
Как реализовать такое?
не хотелось бы лепить кучу циклов в коде... (решето Эратосфена, чтобы разложить на множители, само разложение, перебор чисел, составление пар...)
Заранее благодарен
1. kir55rus - 07 Февраля, 2013 - 17:26:16 - перейти к сообщению
2. EuGen - 07 Февраля, 2013 - 18:34:30 - перейти к сообщению
Если не хочется возиться с большим числом циклов, то Вы, безусловно, можете воспользоваться, к примеру, методом эллиптических кривых или методом общего решета числового поля. Правда их реализация много сложнее решета Эратосфена. И вообще факторизация числа - это NP-полная задача (на текущий момент).
Что же до составления пар- этого и не потребуется. В силу верности утверждения
min(Xi)+min(Yj)<=min(Xi+Yj), x,y>=0, i,j in {N}
- достаточно получить список множителей в отсортированном виде (можете воспользоваться, например, sort) и искомая сумма будет суммой первых двух элементов.
Что же до составления пар- этого и не потребуется. В силу верности утверждения
min(Xi)+min(Yj)<=min(Xi+Yj), x,y>=0, i,j in {N}
- достаточно получить список множителей в отсортированном виде (можете воспользоваться, например, sort) и искомая сумма будет суммой первых двух элементов.
3. Champion - 07 Февраля, 2013 - 22:14:23 - перейти к сообщению
EuGen пишет:
Ну не совсем. В этом примере два первых элемента будет 2 и 3, но они пару не образуют. Лучше все-таки искать минимум в суммах.и искомая сумма будет суммой первых двух элементов.
А по поводу разложения, такое не покатит?
(Добавление)
Но можно разложить и исходное число, и 24 таким способом, а потом, действительно брать по очереди множители исходного числа, если такой же множитель есть и у 24, то отложить его в кучку и убрать из рассмотрения из 24 (только учесть, что и у 24, и у самого исходного числа может быть по несколько одинаковых множителей). Получившаяся последовательность будет состоять из минимальных множителей, которые дадут 24.
Теперь можно циклом, перебрав половину этих множителей получать два числа
div24 и 24/div24 (div24 - это перемноженный на все предыдущие множитель из полученных на предыдущем этапе), найти сумму и сравнить ее с минимальной