Изменения

==== Псевдокод нахождения простых множителей ====

Алгоритм работает за <tex>O(k)</tex>, где k — количество простых множителей.

'''function''' getMultipliers(number: '''int'''): '''vector<int>'''

<font color=green>// сюда складываем множители</font>

result += [probe]

'''return''' result

==== Псевдокод нахождения делителей ====

'''function''' getDividers(number: '''int'''): '''vector<int>'''

<font color=green>// массив полученных делителей</font>

result += [probe]

'''return''' result

=== Улучшенная реализация <tex>O(\sqrt{n})</tex> ===

==== Основная идея ====

Таким образом, любой делитель <tex>d_0 > \sqrt{number}</tex> однозначно связан с некоторым <tex>d_1 < \sqrt{number}</tex>. Если мы найдем все делители до <tex>\sqrt{number}</tex>, задача может считаться решенной.

==== Псевдокод ====

'''function''' getDividers</tex>(number: '''int'''): '''vector<int>'''

result = '''vector<int>'''

result += [number / probe] <font color=green>// <--- записываем сопряженный делитель</font>

'''return''' result

=== Проверка числа на простоту. Множители ===

Алгоритм можно переделать для нахождения простых чисел. Число будет простым, если у него не окажется {{Acronym|множителей|и делителей}} кроме 1 (алгоритмы не проверяют делимость на 1) и самого числа (улучшенная реализация опускает этот делитель). Исключительный случай: <tex>number = 2</tex>.

Решето Эратосфена (англ. ''Sieve of Eratosthenes'') позволяет не только находить простые числа, но и находить простые множители числа. Для этого необходимо хранить (помимо самого "решета") массив простых чисел, на которое каждое число делится (достаточно одного простого делителя).

=== Псевдокод ===

<font color=green>// возвращает только дополнительный массив</font>

'''function''' sieveOfEratosthenes(n: '''int'''): '''int'''[n]

result += [curNum]

'''return''' result

== Источники информации ==