Простые числа до 1000

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

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

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

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

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

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

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

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

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

Для чисел от 2 до 1000 можно заранее ограничить проверку простыми делителями до 31, поскольку √1000 меньше 32. Последовательно проверяют числа 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 и 31. Составной делитель проверять не требуется: если число делится на него, оно делится и на один из его простых множителей.

В решете Эратосфена сначала выписывают числа от 2 до 1000, оставляют 2 и вычёркивают большие кратные 2. Затем берут следующее невычеркнутое число, оставляют его и вычёркивают его большие кратные; так продолжают с 3, 5, 7 и далее. Достаточно обработать простые числа до 31, потому что любое составное число до 1000 имеет простой делитель не больше 31 и будет вычеркнуто.

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

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

Разбор задач

Определить, являются ли числа 37, 51 и 97 простыми

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

1. Для 37: √37 меньше 7, поэтому проверяем 2, 3 и 5. Число не делится ни на один из них, значит, 37 простое.
2. Для 51: √51 меньше 8, поэтому проверяем 2, 3, 5 и 7. 51 делится на 3: 51 = 3 · 17, значит, оно составное.
3. Для 97: √97 меньше 10, поэтому проверяем 2, 3, 5 и 7. Ни на один из них 97 не делится, значит, 97 простое.

Ответ: 37 и 97 — простые числа, 51 — составное.

Найти простые числа от 2 до 100 решетом Эратосфена

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

1. Оставляем 2 и вычёркиваем 4, 6, 8 и остальные большие кратные 2.
2. Следующее невычеркнутое число 3 оставляем и вычёркиваем его большие кратные: 6, 9, 12 и далее.
3. Оставляем 5 и вычёркиваем кратные 5, затем оставляем 7 и вычёркиваем кратные 7.
4. После 7 следующий шаг уже не нужен: √100 = 10, а простые числа до 10 — 2, 3, 5 и 7.

Ответ: остаются числа 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 и 97.

Найти простые делители 840 и разложить число на простые множители

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

1. 840 делится на 2: 840 = 2 · 420, затем 420 = 2 · 210 и 210 = 2 · 105.
2. 105 делится на 3: 105 = 3 · 35, а 35 делится на 5: 35 = 5 · 7.
3. Все полученные множители 2, 3, 5 и 7 простые. Повторяющиеся множители записываем степенями.

Ответ: простые делители 840 — 2, 3, 5 и 7; 840 = 2³ · 3 · 5 · 7.

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

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

Ошибка — проверить число только на 2, 3 и 5 и сразу назвать его простым. Например, 49 не делится на них, но делится на 7. Сначала найдите квадратный корень числа и проверьте все простые делители до него.

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

Ошибка — вычёркивать в решете само найденное простое число вместе с его кратными. Например, после выбора 5 нужно оставить 5, а вычёркивать 10, 15, 20 и другие большие кратные. Перед каждым шагом отделяйте число-основание от его кратных.

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

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

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

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

• Простое число имеет ровно два натуральных делителя: 1 и само себя.
• Число 1 не является ни простым, ни составным.
• Составное число имеет больше двух натуральных делителей.
• Для проверки простоты достаточно проверить простые делители, не превосходящие квадратный корень числа.
• Для чисел до 1000 достаточно проверять делимость на простые числа до 31.
• Решето Эратосфена позволяет быстро получить список простых чисел до 1000.
• Любое составное натуральное число раскладывается на простые множители.