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

Формат:

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

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

Любое натуральное число 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.

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

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

14 ответов к “Разложение числа на множители онлайн”

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

18014398241046527

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

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

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

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

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

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

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

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

Не понимаю, как можно поставить такую задачу в 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 разрядов и выше, иначе первые два метода сработают быстрее).

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

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

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

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

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

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

4 × 2 =