344
правки
Изменения
Нет описания правки
{{Определение | definition=
'''Факторизация ''' (англ. ''factorization'') — представление объекта в виде произведения других объектов.
}}
{{Определение | definition=
'''Разложение на множители''', или '''Факторизация целых чисел ''' (англ. ''integer factorization'') — представление числа в виде [[Основная теорема арифметики#Основная теорема арифметики#Собственно теорема | произведения его множителей]].
}}
== Перебор делителей==
{{Определение | definition=
'''Перебор делителей ''' (англ. ''Trial division'') — алгоритм факторизации или тестирования простоты числа путем полного перебора всех возможных потенциальных делителей.
}}
=== Наивная реализация O(n) ===
result += [curNum]
'''return''' result
== См. также ==
*[[Основная теорема арифметики]]
*[[Дискретная математика, алгоритмы и структуры данных#Комбинаторика | Комбинаторика]]
== Источники информации ==
* Маврин П.Ю. — Лекция по алгоритмам над простыми числами (2016)
* [https://ru.wikipedia.org/wiki/Простое_число https://ru.wikipedia.org/wiki/Простое_число]
[[Категория: Алгоритмы алгебры и теории чисел]]
