Разложение на множители (факторизация) — различия между версиями
(Новая страница: «{{В разработке}} ==Проверка числа на простоту за <tex>O(\sqrt{n})</tex>== ==Разложение на множители за <…») |
(→Проверка числа на простоту за O(\sqrt{n})) |
||
| Строка 2: | Строка 2: | ||
==Проверка числа на простоту за <tex>O(\sqrt{n})</tex>== | ==Проверка числа на простоту за <tex>O(\sqrt{n})</tex>== | ||
| + | |||
| + | Обычно перебор делителей заключается в переборе всех целых (как вариант: простых) чисел от 2 до квадратного корня из факторизуемого числа ''n'' и в вычислении остатка от деления ''n'' на каждое из этих чисел. Если остаток от деления на некоторое число ''m'' равен нулю, то ''m'' является делителем ''n''. В этом случае либо ''n'' объявляется составным, и алгоритм заканчивает работу. | ||
| + | |||
| + | Таким образом, осуществляя проверку на делимость за <tex>O(n)</tex> и перебирая не более <tex>\sqrt{n}</tex> чисел, получаем максимальную оценку времени работы алгоритма: <tex>O(\sqrt{n})</tex>. | ||
==Разложение на множители за <tex>O(\sqrt{n})</tex>== | ==Разложение на множители за <tex>O(\sqrt{n})</tex>== | ||
Версия 08:06, 2 октября 2010
Эта статья находится в разработке!
Проверка числа на простоту за
Обычно перебор делителей заключается в переборе всех целых (как вариант: простых) чисел от 2 до квадратного корня из факторизуемого числа n и в вычислении остатка от деления n на каждое из этих чисел. Если остаток от деления на некоторое число m равен нулю, то m является делителем n. В этом случае либо n объявляется составным, и алгоритм заканчивает работу.
Таким образом, осуществляя проверку на делимость за и перебирая не более чисел, получаем максимальную оценку времени работы алгоритма: .
