24. О простых и составных числах

Определения и обозначения

Натуральный делитель числа — натуральное число, на которое данное число делится без остатка. Например, делители числа 12 — 1, 2, 3, 4, 6 и 12: при делении 12 на каждое из них остатка нет. Перечень делителей помогает определить, простое число или составное.

Простое число — натуральное число, большее 1, имеющее ровно два различных натуральных делителя: 1 и само число. Например, у числа 7 делители только 1 и 7. Это определение позволяет отличить простые числа от тех, которые можно разделить на более мелкие множители.

Составное число — натуральное число, большее 1, имеющее более двух натуральных делителей. Например, у числа 12 есть шесть делителей, поэтому оно составное. Достаточно найти один делитель, кроме 1 и самого числа, чтобы установить составность.

Число 1 не является ни простым, ни составным: у него только один натуральный делитель — оно само. Поэтому его нельзя включить ни в одну из этих групп. При классификации натуральных чисел его всегда рассматривают отдельно.

Как это устроено

Число 1 выделяют отдельно, потому что определения простого и составного числа относятся к числам, большим 1. Кроме того, у единицы только один делитель, тогда как простому нужны ровно два, а составному — больше двух. Если назвать 1 простым, пришлось бы менять определения и усложнять правила разложения чисел на множители.

Чтобы проверить число на простоту, сначала учитывают, что оно должно быть больше 1, а затем ищут его натуральные делители. Само число и 1 делителями являются всегда, поэтому проверяют, найдётся ли ещё хотя бы один. Если других делителей нет, число простое; если они есть, оно составное.

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

При проверке простоты не обязательно перебирать числа до самого проверяемого числа. Если число n составное, его можно представить произведением двух натуральных множителей; они не могут оба быть больше √n, потому что тогда их произведение было бы больше n. Значит, хотя бы один нетривиальный делитель не превосходит √n. Проверив делители до этого значения, можно либо найти делитель, либо обоснованно заключить, что число простое.

Решето Эратосфена — способ найти все простые числа в заданном диапазоне, последовательно вычёркивая составные. Записывают числа от 2 до границы, оставляют первое ещё не вычеркнутое число, а его кратные вычёркивают. Затем переходят к следующему оставшемуся числу и снова убирают его кратные. Достаточно продолжать, пока квадрат выбранного простого не превысит верхнюю границу: у каждого составного числа в диапазоне уже будет вычеркнут меньший делитель.

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

Сначала проверьте условие для числа: простым или составным может быть только натуральное число больше 1. Затем посмотрите на количество делителей: ровно два означает простое, больше двух — составное. У единицы один делитель, поэтому для неё в таблице указана отдельная колонка.

Разбор задач

Задача 1. Определите, является ли число 17 простым или составным.

1. Число 17 больше 1, поэтому оно может быть простым или составным.
2. Проверим делители до √17. Так как 4² = 16, а 5² = 25, достаточно проверить делимость на 2, 3 и 4.
3. 17 не делится на 2, потому что оно нечётное; на 3 — потому что сумма его цифр равна 8; на 4 — потому что последние две цифры 17 не делятся на 4.
4. Других нетривиальных делителей быть не может: если бы они существовали, один из них был бы не больше √17.

Ответ: 17 — простое число, его делители только 1 и 17.

Задача 2. Определите, является ли число 39 простым или составным.

1. Число 39 больше 1, поэтому нужно проверить, есть ли у него делитель, кроме 1 и 39.
2. Сложим цифры: 3 + 9 = 12. Число 12 делится на 3, значит, по признаку делимости на 3 на 3 делится и 39.
3. Проверим деление: 39 : 3 = 13, остатка нет. Делитель 3 не равен ни 1, ни самому числу 39.
4. Найденного делителя достаточно: у 39 есть как минимум делители 1, 3, 13 и 39.

Ответ: 39 — составное число.

Задача 3. С помощью решета Эратосфена найдите все простые числа от 2 до 50.

1. Запишем числа от 2 до 50. Поскольку √50 меньше 8, достаточно вычёркивать кратные простым числам 2, 3, 5 и 7.
2. Оставим 2 и вычеркнем остальные числа, кратные 2; затем оставим 3 и вычеркнем её кратные, которые ещё не зачёркнуты.
3. Оставим 5 и вычеркнем кратные 5; после этого оставим 7 и вычеркнем её кратные. Само каждое найденное простое число не вычёркиваем.
4. После этих действий незачёркнутыми останутся числа, которые не делятся на проверенные простые и потому не имеют делителей до √50.

Ответ: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.

Типичные ошибки

Иногда число 1 называют простым, потому что оно делится на себя и на 1. Но это одно и то же число, поэтому у него не два различных делителя, а только один. Сверяйтесь с определением: для простоты нужны ровно два различных делителя, и число должно быть больше 1.

Чётность сама по себе не означает, что число составное: число 2 делится на 2 и при этом имеет только делители 1 и 2. Ошибку допускают, забывая, что делитель может совпадать с самим числом. Чтобы проверить себя, отдельно рассмотрите 2, а для чётного числа больше 2 найдите делитель 2, отличный от самого числа.

При проверке простоты нельзя считать делитель, равный самому числу, признаком составности. Он есть у любого натурального числа, как и делитель 1. Ищите только нетривиальный делитель — натуральное число, отличное и от 1, и от проверяемого числа.

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

Связь с другими темами

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

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

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

Что запомнить

• Простое число больше 1 и имеет ровно два натуральных делителя.
• Составное число больше 1 и имеет более двух натуральных делителей.
• Число 1 не является ни простым, ни составным.
• Чтобы доказать составность числа, достаточно указать один нетривиальный делитель.
• Если у числа есть нетривиальные делители, один из них не превосходит квадратного корня из числа.
• Решето Эратосфена позволяет находить простые числа в заданном диапазоне.