Разложение натурального числа на простые множители
Внимание! Это довольно старый топик, посты в него не попадут в новые, и их никто не увидит. Пишите пост, если хотите просто дополнить топик, а чтобы задать новый вопрос — начните новый.
Внимание! Это довольно старый топик, посты в него не попадут в новые, и их никто не увидит. Пишите пост, если хотите просто дополнить топик, а чтобы задать новый вопрос — начните новый.
В раздел «Готовые решения» добавил «Разложение натурального числа на простые множители».
Решение можно обсудить в этой теме.
Почему выбран std::vector? Мне кажется, лучше взять std::map, где ключ — простое число в разложении, а значение — степень числа.
Ещё. Разве возвращать std::vector — не затратная операция? Мне кажется, лучше возвращать указатель, или передавать по ссылке в функцию std::vector для вывода результата туда?
porshe, если честно, про
vectorя думал меньше всего )) Просто мне нужна была некая структура данных нефиксированного размера для хранения результатов.vectorилиmap— дело вкуса и/или удобства дальнейшего использования, как и возвратvector. К алгоритму факторизации это не относится.Собственно говоря, данное «готовое решение» — это сам алгоритм факторизации, а способ хранения и/или возврата результата — рюшечки. Можно вообще сразу на консоль выводить ))
Ну тогда, у меня больше нет претензий)
В данном случае будет NRVO, или, в крайнем случае, перемещение.
Тут ещё стоит принять во внимание, что даже если компилятором не будет делаться никаких оптимизаций, возвращаемый вектор будет сравнительно небольшого размера: для самого невыгодного случая 2^63 (больше в
unsigned __int64не поместится) — размер вектора 63 элемента — ерунда, даже если он будет честно копироваться.Если же переключиться на арифметику произвольной длины (с помощью соответствующей библиотеки) и, допустим, попытаться «поломать» RSA-числа (надо сказать, с этим алгоритмом факторизации — занятие совершенно бесперспективное), то время на отыскание разложения перекроет время копирования вектора с бо-о-ольшим гаком.
Если рассматривать отвлечённо возврат вектора и передачу вектора в функцию по ссылке, то, спору нет, выгоднее работать со ссылкой. Опять-таки не учитывая оптимизацию.
porshe, меня заинтересовало твоё предложение "лучше возвращать указатель". Что ты имел ввиду?
Имел ввиду возвращать указатель на выделенную память под вектор внутри функции (или возвращать умный указатель).