Нещодавно встала така задача:
Дано якесь позитивне число, треба знайти всі його подільники, крім його самого.
Завдання в тому щоб написати якомога швидший алгоритм, і звичайно ж
коректний.
Перша ідея була, перебирати менші числа, перевіряючи на подільність, але повний
перебір не дав широких меж застосування, вже для вирішення завдання наприклад для
, цей алгоритм працював дуже довго, після кількох модифікацій
я отримав ось такий ось алгоритм, верхня оцінка складності в гіршому випадку.
Алгоритм заповнює вектор детелей числа.
void find_divs (int n, vector
divs.push_back (1);
Чи можна якось поліпшити алгоритм? Або є більш швидкі методи вирішення цього завдання?
Re: Знаходження всіх дільників числа
Чи можна якось поліпшити алгоритм?
Для початку треба б його виправити. Перевірте, що у вас вийде для 12 і 36.
Або є більш швидкі методи вирішення цього завдання?
Спочатку отримайте розкладання вхідного числа на прості множники. Далі перебирає всі комбінації простих множників.
Re: Знаходження всіх дільників числа
Для початку треба б його виправити. Перевірте, що у вас вийде для 12 і 36.
Так, алгоритм працює неправильно). Думаю ця правильна:
void find_divs (int n, vector
divs.push_back (1);
Спочатку отримайте розкладання вхідного числа на прості множники. Далі перебирає всі комбінації простих множників.
Так, була така ідея, на перебір комбінацій піде десь ітерацій, як в цьому випадку оцінити складність алгоритму? Чи є якась формула для обчислення кількості простих множників числа. Або хоча б треба оцінити верхню межу, тобто знайти число, яке розкладається на максимальне число простих множників.