Статью подготовили специалисты образовательного сервиса Zaochnik.
Простые и составные числа, определения, примеры, таблица простых чисел, решето Эратосфена
Содержание:
- 27 мая 2023
- 10 минут
- 4840
В статье рассматриваются понятия простых и составных чисел. Даются определения таких чисел с примерами. Приводим доказательство того, что количество простых чисел неограниченно и произведем запись в таблицу простых чисел при помощи метода Эратосфена. Будут приведены доказательства того, является ли число простым или составным.
Простые и составные числа – определения и примеры
Простые и составные числа относят к целым положительным. Они обязательно должны быть больше единицы. Делители также подразделяют на простые и составные. Чтобы понимать понятие составных чисел, необходимо предварительно изучить понятия делителей и кратных.
Единица не является ни простым ни составным числом. Она имеет только один положительный делитель, поэтому отличается от всех других положительных чисел. Все целые положительные числа называют натуральными, то есть используемые при счете.
Любое число, которое больше является либо простым, либо составным. Из свойства делимости имеем, что и число а всегда будут делителями для любого числа , то есть оно будет делиться само на себя и на . Дадим определение целых чисел.
Простые числа: . Они делятся только сами на себя и на . Составные числа: . То есть число можно разложить на и , а на , а на , то есть его делители будут . Число разложится на и . Заметим, что понятия простых чисел и взаимно простых чисел – разные понятия.
Таблица простых чисел
Для того, чтобы было проще использовать простые числа, необходимо использовать таблицу:
Таблица для всех существующих натуральных чисел нереальна, так как их существует бесконечное множество. Когда числа достигают размеров или , тогда следует задуматься об использовании решета Эратосфена.
Рассмотрим теорему, которая объясняет последнее утверждение.
Так как простых чисел очень много, то таблицы ограничивают числами и так далее.
Решето Эратосфена
При составлении таблицы простых чисел следует учитывать то, что для такой задачи необходима последовательная проверка чисел, начиная с до . При отсутствии делителя оно фиксируется в таблицу, если оно составное, то в таблицу не заносится.
Рассмотрим пошагово.
Если начать с числа , то оно имеет только делителя: и 1, значит, его можно занести в таблицу. Также и с числом . Число является составным, следует разложить его еще на и . Число является простым, значит, можно зафиксировать в таблице. Так выполнять вплоть до числа .
Данный способ неудобный и долгий. Таблицу составить можно, но придется потратить большое количество времени. Необходимо использовать признаки делимости, которые ускорят процесс нахождения делителей.
Способ при помощи решета Эратосфена считают самым удобным. Рассмотрим на примере таблиц, приведенных ниже. Для начала записываются числа .
Теперь необходимо зачеркнуть все числа, которые кратны . Произвести последовательное зачеркивание. Получим таблицу вида:
Далее вычеркиваем все числа, кратные . Получаем таблицу вида:
Переходим к вычеркиванию чисел, кратных . Получим:
Вычеркиваем числа, кратные . В конечном итоге таблица получает вид
Перейдем к формулировке теоремы.
Из доказанной теоремы видно, что вычеркивание чисел в таблице приводит к тому, что необходимо начинать с числа , которое равняется и удовлетворяет неравенству . То есть, если вычеркнуть числа, кратные , то процесс начинается с , а кратных – с и так далее до .
Составление такой таблицы при помощи теоремы Эратосфена говорит о том, что при вычеркивании всех составных чисел, останутся простые, которые не превосходят . В примере, где , у нас имеется, что . Отсюда и получаем, что решето Эратосфена отсеивает все составные числа, которые по значению не больше значения корня из . Поиск чисел производится при помощи вычеркивания.
Данное число простое или составное?
Перед решением необходимо выяснять, является ли число простым или составным. Зачастую используются признаки делимости. Рассмотрим это на ниже приведенных примере.
Такие признаки не способны доказать простоту числа. Если нужна проверка, следует производить другие действия. Самый подходящий способ – это перебор чисел. В течение процесса можно найти простые и составные числа. То есть числа по значению не должны превосходить . То есть число а необходимо разложить на простые множители. если это будет выполнено, тогда число а можно считать простым.
Навигация по статьям