Перебор делителей

Перебор делителей
У этого термина существуют и другие значения, см. Перебор.

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

Описание алгоритма

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

Практическое применение

В практических задачах данный алгоритм применяется редко ввиду его большой асимптотической сложности (в О-нотации), однако его применение оправдано в случае, если проверяемые числа относительно невелики, так как данный алгоритм довольно легко реализуем.

Примечания

  1. ↑ Легко заметить, что если у n есть некоторый делитель p, то n/p так же будет делителем, причём один из этих делителей не превосходит \sqrt{n}.
Логотип Викиучебника
Имеется викиучебник по теме
«Программные реализации перебора делителей»


Формула

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Полезное


Смотреть что такое "Перебор делителей" в других словарях:

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

  • Перебор (значения) — Перебор: Полный перебор  общий метод решения задач путем перебора всех возможных потенциальных решений. В частности: Перебор делителей  алгоритм факторизации и тестирования простоты в вычислительной математике. Метод перебора  простейший алгоритм …   Википедия

  • Полный перебор — У этого термина существуют и другие значения, см. Перебор. Полный перебор (или метод «грубой силы», англ. brute force)  метод решения математических задач. Относится к классу методов поиска решения исчерпыванием всевозможных… …   Википедия

  • Прямой перебор — Полный перебор (или метод «грубой силы» от англ. brute force) метод решения задачи путем перебора всех возможных вариантов. Сложность полного перебора зависит от размерности пространства всех возможных решений задачи. Если пространство решений… …   Википедия

  • Последовательное деление — Перебор делителей алгоритм факторизации или тестирования простоты числа путем полного перебора всех возможных потенциальных делителей. Обычно перебор делителей заключается в переборе всех целых (как вариант: простых) чисел от 2 до квадратного… …   Википедия

  • Тест простоты — Тест простоты  алгоритм, который по заданному натуральному числу определяет, простое ли это число. Различают детерминированные и вероятностные тесты. Определение простоты заданного числа в общем случае не такая уж тривиальная задача. Только… …   Википедия

  • Решето Эратосфена — алгоритм нахождения всех простых чисел до некоторого целого числа n, который приписывают древнегреческому математику Эратосфену Киренскому. Содержание 1 Алгоритм …   Википедия

  • Метод квадратичных форм Шенкса — метод факторизации целых чисел, основанный на применении квадратичных форм, разработанный Даниелем Шенксом (англ. Daniel Shanks).[1] в 1975 году, как развитие метода факторизации Ферма. Для 32 разрядных компьютерах алгоритмы, основанные на… …   Википедия

  • Брутер, Брутофорс — Полный перебор (или метод «грубой силы» от англ. brute force) метод решения задачи путем перебора всех возможных вариантов. Сложность полного перебора зависит от размерности пространства всех возможных решений задачи. Если пространство решений… …   Википедия

  • Брутфорс — Полный перебор (или метод «грубой силы» от англ. brute force) метод решения задачи путем перебора всех возможных вариантов. Сложность полного перебора зависит от размерности пространства всех возможных решений задачи. Если пространство решений… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»