Разложение числа на простые множители онлайн

Любое натуральное число n > 1 можно представить в виде произведения простых чисел. Это представление называется разложением числа n на простые множители.
Число:
Вид записи: Кратко
Подробно
В столбик
Результат:


Натуральное число n называется делителем целого числа m, если для подходящего целого числа k верно равенство m = n \cdot k. В этом случае говорят, что m делится на n или что число m кратно числу n.

Простым числом называют натуральное число p \ge 2, делящееся только на себя и на единицу. Составным числом называют число, имеющее больше двух различных делителей (любое натуральное число m, не равное 1, имеет как минимум два делителя: 1 и |m|). Например, числа 2, 3, 5, 7, 11 – простые, а числа 9 = 3\cdot 3, 26 = 2\cdot 13 – составные.

Основная теорема арифметики. Любое натуральное число n, большее единицы, можно разложить в произведение простых чисел, причём это разложение единственно с точностью до порядка следования сомножителей.

Данная программа раскладывает число в произведение простых множителей онлайн. Разложить число на множители онлайн с её помощью очень просто.

Как разложить число на множители?

В школе на уроках математики разложение числа на множители обычно записывают столбиком (в две колонки). Делается это так: в левую колонку выписываем исходное число, затем

  • Берём самое маленькое простое число — 2 и по признакам делимости или обычным делением проверяем, делится ли исходное число на 2.
  • Если делится, то в правую колонку выписываем 2. Далее делим исходное число на 2 и записываем результат в левую колонку под исходным числом.
  • Если не делится, то берём следующее простое число — 3.

Повторяем эти шаги, при этом работаем уже с последним числом в левой колонке и с текущим простым числом. Разложение заканчивается, когда в левой колонке будет записано число 1.

Чтобы лучше понять алгоритм, разберём несколько примеров.

Пример. Разложить на множители число 84.

Решение. Записываем число 84 в левую колонку:

84

Берём первое простое число — два и проверяем, делится ли 84 на 2. Так как 84 оканчивается на 4, а 4 делится на 2, то и 84 делится на 2 по признаку делимости. Записываем 2 в правую колонку. 84:2 = 42, число 42 записываем в левую колонку. Получили вот что:

84
42
2

Теперь работаем уже с числом 42. Число 42 делится на 2, поэтому записываем 2 в правую колонку, 42:2 = 21, число 21 записываем в левую колонку.

84
42
21
2
2

Число 21 на 2 не делится, поэтому проверяем его делимость на следующее простое число — 3. Число 21 делится на 3, 21:3 = 7. Записали 3 в правую колонку, 7 — в левую. Получили

84
42
21
7
2
2
3

Число 7 — простое число, поэтому в правой колонке записываем 7, в левую пишем 1. В итоге получили:

84
42
21
7
1
2
2
3
7

Всё, число разложено!

В результате в правой колонке оказались записаны все простые множители числа 84. То есть 84=2∙2∙3∙7.

О калькуляторе

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

Разложение числа на простые множители онлайн: 13 комментариев

  1. Анастасия

    Программа хорошая. Один вопрос. На каком языке написана программа?

  2. Евгений

    18014398241046527

    Результат: Число 18014398241046528 — простое.

    Согласен, что заданное число — простое, но в результате вообще указано четное число. 🙂

    1. Андрей Автор записи

      Евгений, программа была исправлена, сейчас работает корректно. Однако если в разложении числа присутствует большое простое число, то разложение может идти долго.

  3. GoodWeather

    Я не понимаю хоть убейте — что такое «с точностью до порядка следования сомножителей»?? Что за «порядок»?? Какого ещё «следования»??
    > 90 == 5 * 3 * 3 * 2.
    Что здесь «порядок следования»??
    Ну вот другой порядок следования, и чего?:
    > 90 == 2 * 3 * 5 * 3.

    1. Андрей Автор записи

      > 90 == 5 * 3 * 3 * 2.
      > 90 == 2 * 3 * 5 * 3.

      Формулировка «с точностью до порядка следования сомножителей» означает, что нам важен не порядок, в котором идут простые множители числа, а важно количество раз, которое каждый простой множитель встречается в разложении числа.

      В примере с числом 90 в разложении присутствует один множитель 2, два множителя 3 и один множитель 5. Когда говорят, что разложение единственно, то имеют в виду, что не существует разложения числа 90, в котором было бы, например, два множителя 2.

  4. Елена

    Добрый день! 6 класс, задание на контрольной. Необходимо разложить число 253 426. Возможно ли без нескончаемых проверок на деление определить, что число 126 713 (результат деления заданного числа на 2) и есть простой множитель?

    1. Шурик

      Не понимаю, как можно поставить такую задачу в 6-м классе… Либо неверно истолковано условие, либо я слишком «закостенел»:
      1. Все методы проверки числа на простоту — вероятностные (т.е. не 100%-ные)
      2. Грубо говоря, есть только 3 рабочих метода разложения чисел на множители:
      — последовательный перебор;
      — метод Ферма (A^2 - N = B^2, где N — ваше число, A\sqrt{N} + 1, \sqrt{N} + 2, \sqrt{N} + 3,\ldots, а \sqrt{N} — округлённый вверх корень из числа N);
      — квадратичное решето (это экзотика для разложения чисел от 100 разрядов и выше, иначе первые два метода сработают быстрее).

      1. Андрей Автор записи

        Да, полностью согласен с Шуриком, мы не знаем способа, который позволил бы с уверенностью определить, что число 126 713 является простым, не прибегая к многочисленным проверкам на деление.

        На мой взгляд, самым быстрым способом в данном случае является проверка, делится ли 126 713 на простые числа от 2 до \lfloor\sqrt{126713}\rfloor = 355. Делители проверяем только до квадратного корня потому, что если число составное, то его можно представить как произведение n = a \cdot b, где a и b — целые числа больше 1, и одно из этих чисел точно не больше \lfloor\sqrt{n}\rfloor.

        Всего имеется 71 простых чисел, не превышающих 355, но вручную за разумное время проверить делимость на 71 число не представляется возможным.

        Существует тест Агравала — Каяла — Саксены, позволяющий протестировать число на простоту быстрее описанного выше алгоритма — но есть несколько НО — этот тест хорошо работает на компьютере и для действительно больших чисел.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

два × 2 =