Изменения

''Факторизация'' (англ. ''factorization'') — представление объекта в виде произведения других объектов.

''Разложение на множители'', или ''Факторизация целых чисел'' (англ. ''integer factorization'') — представление числа в виде [[Основная теорема арифметики#Основная теорема арифметики#Собственно теорема | произведения его множителей]].

Перебор делителей (англ. ''Перебор делителейTrial division'' ) — алгоритм факторизации или тестирования простоты числа путем полного перебора всех возможных потенциальных делителей.

 == Перебор делителей = Наивная реализация O(англ. ''Trial division''n)====== Наивная реализация [[Основная теорема арифметики#Основная теорема арифметики#Собственно теорема | Основная теорема арифметики]], в купе с утверждением, что <tex>\forall x, y \in \mathbb{N}~~x<y \Longrightarrow</tex> {{Acronym|<tex>O\left(n\dfrac{x}{y} < 1 \right)</tex> ===|т.е. y не делит x нацело}}, позволяют нам ограничить пространство поиска делителей числа <tex>number</tex> интервалом [2; <tex>number</tex>].

[[Основная теорема арифметики#Основная теорема арифметики#Собственно теорема | Основная теорема арифметики]], в купе с утверждениемЗаметим, что если <tex>\forall x, y \in \mathbb{N}~~x<y \Longrightarrow</tex> {{Acronym|<tex>\left( \dfrac{x}{y} < 1 \right)</tex>|т.е. y не делит x нацело}}, позволяют нам ограничить пространство поиска делителей числа <tex>\mathtt{number}</tex> интервалом <tex>[2; \mathtt{number}]</tex>. Заметим, что если = <tex>\mathtt{number} = \prod p_i = p_1 * \cdot p_2 * \dots * cdot \ldots \cdot p_{j-1} * \cdot p_j * \cdot p_{j+1} * \dots * cdot \ldots \cdot p_n</tex>, то <tex>\left(\dfrac{\mathtt{number}}{p_i}\right) = \prod\limits_{i \ne j} p_i = p_1 * \cdot p_2 * \dots * cdot \ldots \cdot p_{j-1} * \cdot p_{j+1} * \dots * cdot \ldots \cdot p_n</tex>. Таким образом, мы можем делить <tex>\mathtt{number}</tex> на его {{Acronym|делители|множители}} последовательно и в любом порядке. Тогда будем хранить <tex>\mathtt{curNum} \colon curNum \mathtt{curNum} * cdot \prod \mathtt{result_i} =\mathtt{number}</tex> — произведение оставшихся множителей.

Из определения: <tex>\sqrt{n} * \cdot \sqrt{n} = n</tex>. Логично, что:

|<tex>x * \cdot y = number</tex>