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

— Сова, спасибо тебе большое за науку, — поблагодарил ту Винни-Пух, — теперь мы с Пятачком без труда сможем разделить наш мёд, так, чтобы и мне хватило на зиму, и Пятачку было не стыдно поехать к своей кузине Пеппе.

Но, посчитав свои запасы, медведь со своим другом пребывали в замешательстве. Это заметила Сова.

— Что случилось Винни? Полученных вами знаний должно хватить, чтобы разделить мёд.

— У нас возникла проблема, — начал Пятачок, — то количество банок мёда, которое имеется в подвале у Винни нельзя разделить ни на 2, ни на 3, ни вообще, ни на какое число.

— Совсем забыла, — виновато сказала Сова, — старая уже стала. Не рассказала вам о простых и составных числах.    

Из предыдущих уроков нам уже известно, что деление и умножение являются обратными арифметическими операциями:

А:В=n; А=В·n

например, 65:13=5; 65=13·5

Если натуральное число А (делимое) делится на другое натуральное число В (делитель), то результатом деления будет натуральное число n (частное), такое, что произведение B на n даст А.

Другими словами можно сказать, что в А содержится В, повторённое n раз. Или В кратно А — n раз.

Мы уже говорили о том, что не все натуральные числа делятся на другие натуральные числа нацело.

Например, 12:4=3 – в 12-ти четвёрка «умещается» 3 раза.

А вот 13 на 4 уже не делится нацело – в 13-ти четвёрка умещается 3 раза, но при этом ещё остаётся 1 (единица), которая называется остатком.

— А есть такие натуральные числа, которые не делятся нацело ни на какое другое число? – спросил любопытный Пятачок.

— Нет, Пятачок, таких чисел нет, ведь любое число делится на 1 и на самое себя:

А:1=А; А:А=1

Например, 12:1=12; 12:12=1 или 13:1=13; 13:13=1.

Любое натуральное число имеет хотя бы два делителя – единицу и самое себя.

Единственным исключением является число 1, которое имеет один делитель – 1.

Число 2 имеет два делителя: 1 и 2 – 2:1=2; 2:2=1.

Число 3 имеет также два делителя: 1 и 3 – 3:1=3; 3:3=1.

А вот число 4 уже имеет три делителя: 1, 2 и 4 – 4:1=4; 4:2=2; 4:4=1.

    Натуральные числа, имеющие только два делителя (1 и самое себя) называются простыми числами.   Натуральные числа, имеющие больше двух делителей, называются составными числами.    

Число 1 не относится ни к простым, ни к составным числам.

Число 2 является единственным чётным простым числом.

Все чётные числа, большие 2, являются составными числами, поскольку все они делятся на 1, на самое себя и на 2 (см. признаки делимости).

— А как можно выучить простые числа? – спросил заинтригованный Пух.

— К сожалению, Винни, простые числа нельзя   выучить как таблицу умножения, — огорчила медведя Сова. – Их слишком много, бесконечно много и они не имеют никакой закономерной последовательности.

— А как же их находят? – хором спросили удивленные медведь с поросёнком?

— Очень просто, — с помощью решета Эратосфена, — ответила мудрая Сова изумлённым слушателям.

Давным-давно, в Древней Греции жил великий математик того времени, которого звали Эратосфен. В III веке еще до нашей эры Эратосфен придумал способ нахождения простых чисел, которым пользуются до сих пор.

Современная наука, используя принцип решета Эратосфена,   составила таблицы, насчитывающие миллионы простых чисел.

Решето Эратосфена

Принцип работы решета Эратосфена достаточно прост.

Для примера найдём все простые числа на промежутке от 1 до 50.

Запишем все числа, начиная с 2, и заканчивая 50 (1 не является ни простым, ни составным числом):

Числа 2 и 3 (об этом мы уже сказали) – простые, обводим их зелёным цветом.

Также мы сказали, что все остальные чётные числа являются составными числами – вычёркиваем их (красный цвет):

Дальше вычёркиваем все числа, кратные 3, они также будут составными:

Первое не зачёркнутое число – 5, оно будет простым, т. к. не делится на меньшие числа кроме 1. Вычёркиваем все числа, кратные 5:

Первое не зачёркнутое число – 7, оно простое, т. к. не делится на меньшие числа кроме 1. Вычёркиваем числа, кратные 7:

Дальше делать проверку не имеет смысла – все оставшиеся не зачёркнутые числа будут простыми.

Почему?

Дело в том, что 7·7=49, а 50 – составное число. Если бы в промежутке от 7 до 49 осталось какое-то не зачёркнутое составное число, оно должно иметь делитель 7 или меньше. Но мы все числа, кратные числам 2, 3, 5,  7 уже перебрали и вычеркнули. Поэтому, после 7 остались только числа, которые не имеют делителей в диапазоне от 2 до 7. Первое составное (из не зачёркнутых) чисел после 7 будет 49 (квадрат семёрки), поэтому, всё, что осталось не зачёркнутым в интервале от 7 до 49 – будут простыми числами.

Таков принцип нахождения простых чисел при помощи решета Эратосфена, через которое «просеиваются» составные числа.

Например, чтобы найти простые числа от 2 до 1000 надо будет сделать 11 «шагов», перебрав и вычеркнув составные числа, кратные простым числам: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31.

Почему? Потому, что 32·32=1024, что уже больше 1000.

Таблица простых чисел от 2 до 1000:

Любое составное число можно разложить на простые множители.

Порядок разложения чисел на простые множители

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

Определяется, делится ли исходное число на 2? Если делится, то производится деление, и дальше работают с получившимся частным. Если исходное число не делится на 2, проверяется признак деления на 3 и т. д.

Для примера разложим число 100 на простые множители:

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

100 делится на 2? Да. 100:2=50.

50 простое число? Нет, значит, продолжаем разложение.

50 делится на 2? Да. 50:2=25.

25 простое число? Нет, значит, продолжаем разложение.

25 делится на 2? Нет.

25 делится на 3? Нет.

25 делится на 5? Да. 25:5=5.

5 простое число? Да. 5:5=1. Разложение закончено.

100=2·2·5·5

В качестве еще одного примера разложим на простые множители число 253.

Смотрим по таблице простых чисел, является ли число 253 простым? Нет. Значит, его можно разложить на простые множители.

253 делится на 2? Нет, т. к., последняя цифра нечётная.

253 делится на 3? Нет, т. к, сумма цифр не кратна 3.

253 делится на 5? Нет, т. к, последняя цифра не является ни 5, ни 0.

253 делится на 7? Нет.

253 делится на 11? Да. 253:11=23.

23 является простым числом? Да. 23:23=1.

Разложение закончено.

Число 253 можно разложить на два простых множителя:

253=11·23.

Для ускорения разложения числа, заканчивающегося нулем, на простые множители, можно сразу записывать два простых множителя 2 и 5, поскольку 2·5=10, после чего у исходного числа отбрасывать последний нуль, и продолжать разложение.