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

Простые и составные числа

Базовое понятие, с которым необходимо познакомиться, - это что такое простые и что такое составные числа. Простое число - это число, которое без остатка делится только на себя и на единицу. Составное число - это число, у которого есть делитель отличный от себя и единицы. Например, число 17 - простое, а 27 - составное, так как 27 vdots 3.

Запомните, что единица не относится ни к простым, ни к составным числам! Понятие простое/составное применимо только для натуральных чисел, ~>=2.

Теперь мы ввести понятие "разложить на простые множители". Это значит, представить число как произведение простых чисел. Делается это очень просто: мы представляем число как произведение хоть каких-нибудь множителей, а дальше каждый множитель "дробим" до тех пор, пока не получится произведение только из простых чисел. Кстати, для подбора хоть какого-нибудь делителя нам помогут признаки делимости.

К слову, существует теорема, которая называется основная теорема арифметики: У любого натурального числа большего 1, существует единственное разложение на простые множители. Это знание позволяет раскладывать нам число так, как нам удобно, не боясь получить разные разложения.

Запомните, у каждого числа всего одно разложение на простые множители!

Например: 216=4*54=(2*2)*(6*9)=2*2*(2*3)*(3*3)=2^3*3^3
Или: 2600=26*10*10=(2*13)*(2*5)*(2*5)=2^3*5^2*13

Разложение на простые множители. Повышенный уровень

Немного сложнее дело обстоит с разложением на простые множители чисел типа 667 или 3127. Дело в том, что ни один признак делимости на небольшие числа не "выдаст" Вам, на что делится каждое из этих число, потому что они оба - произведение сравнительно крупных простых чисел: 667=23*29, а 3127 = 53*59. Пытаясь найти, на что делится любое из этих чисел, нам ничего не остаётся, кроме как пробовать делить его на всё большие и большие простые множители. Однако, данный перебор может быть довольно долгим и утомительным. А если это число на самом деле простое, и мы не найдём его делителя? Неужели перебирать необходимо до самого исследуемого числа?

Ответ - нет! Есть теорема, которая ограничивает данный перебор, правда она для тех, кто знает, что такое "квадратный корень":
У любого составного числа есть делитель не превосходящий квадратного корня их этого числа.

Пользоваться ей очень просто:

  1. Определяем корень из исследуемого числа (желательно взять с небольшим перебором)
  2. Перебираем все простые числа до этого корня в качестве делителя исходного числа
  3. Если оно поделилось на кого-то, то вот оно - искомое разложение на множители (не обязательно простые)
  4. Если ни на кого не поделилось, то делаем вывод, что исходное число является простым.

Например, для числа 3127 корень можно оценить числом 60, то есть пробовать делить его необходимо только на простые числа до 60, среди которых мы наткнёмся на 53, на которое оно поделится.

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

×

Вход в систему