Разложение на множители (факторизация) — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Разложение на множители за O(\sqrt{n}))
Строка 9: Строка 9:
 
==Разложение на множители за <tex>O(\sqrt{n})</tex>==
 
==Разложение на множители за <tex>O(\sqrt{n})</tex>==
  
Для поиска разложения числа на множители воспользуемся так же простым перебором чисел от <tex>1</tex> до <tex>\sqrt{n}</tex>. С помощью алгоритма проверки простоты найдём первый делитель числа <tex>n</tex> - <tex>m</tex>. Далее <tex>n</tex> сокращается в <tex>m</tex> раз и процедура повторяется. По достижении квадратного корня из <tex>n</tex> и невозможности сократить <tex>n</tex> ни на одно из меньших чисел, <tex>n</tex> объявляется неразложимым.
+
Для поиска разложения числа на множители воспользуемся так же простым перебором чисел от <tex>1</tex> до <tex>\sqrt{n}</tex>. С помощью алгоритма проверки простоты найдём первый делитель <tex>m</tex> числа <tex>n</tex>. Далее <tex>n</tex> сокращается в <tex>m</tex> раз и процедура повторяется. По достижении квадратного корня из <tex>n</tex> и невозможности сократить <tex>n</tex> ни на одно из меньших чисел, <tex>n</tex> объявляется неразложимым.

Версия 08:14, 19 февраля 2011

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

Проверка числа на простоту за [math]O(\sqrt{n})[/math]

Обычно перебор делителей заключается в переборе всех целых (как вариант: простых) чисел от 2 до квадратного корня из факторизуемого числа n и в вычислении остатка от деления n на каждое из этих чисел. Если остаток от деления на некоторое число m равен нулю, то m является делителем n. В этом случае либо n объявляется составным, и алгоритм заканчивает работу.

Таким образом, осуществляя проверку на делимость за [math]O(n)[/math] и перебирая не более [math]\sqrt{n}[/math] чисел, получаем максимальную оценку времени работы алгоритма: [math]O(\sqrt{n})[/math].

Разложение на множители за [math]O(\sqrt{n})[/math]

Для поиска разложения числа на множители воспользуемся так же простым перебором чисел от [math]1[/math] до [math]\sqrt{n}[/math]. С помощью алгоритма проверки простоты найдём первый делитель [math]m[/math] числа [math]n[/math]. Далее [math]n[/math] сокращается в [math]m[/math] раз и процедура повторяется. По достижении квадратного корня из [math]n[/math] и невозможности сократить [math]n[/math] ни на одно из меньших чисел, [math]n[/math] объявляется неразложимым.