Переключить меню

В этот статье мы сделаем экскурс в алгоритмы поиска простых чисел и рассмотрим один из алгоритмов, который реализует такой поиск. Этот метод поиска получил название "", в честь древнегреческого математика Эратосфена Киренского. А "решето" потому, что мы как бы просеиваем массив чисел, оставляя в нем только простые числа.

Вспомним, что простым числом , является число, которое без остатка может делиться только само на себя, ну и, конечно же, на единицу. Из школьного курса вы, наверное, помните некоторые из простых чисел - это 5, 7, 11, 13, 17 и так далее. Давайте теперь рассмотрим сам принцип работы алгоритма поиска простых чисел. Этот метод поиска достаточно прост, поэтому, при желании, вам все станет очень скоро понятно.

Решето Эратосфена - алгоритм работы. Язык программирования С++

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

Const int size = 1000; bool array;

2. Теперь нам нужно присвоить начальные значения элементам массива, т.к. на данный момент они содержат различный системный "мусор". Поступим так: присвоим всем элементам массива значения "true" - истина или единица. По мере работы алгоритма поиска простых чисел, все элементы массива (они у нас изначально установлены в true) с "простыми" индексами (заметьте, что здесь речь идет именно об индексах, т.к. наши искомые простые числа у нас будут выражаться в значениях индексов элементов массива) останутся быть равными "true", а все остальные установятся в "false" - ложь, или нуль. Т.е. теперь вы поняли, почему массив у нас содержит логические значения, а если и что-то не понятно, то, разобрав код, все встанет на свои места. Заполняем массив, начиная со второй ячейки, т.к. 0 и 1 не относят к простым, а значит и можно сразу их исключить

For(int k = 2; k < size; k++) array[k] = true;

3. А теперь самое важное: рассмотрим сам алгоритм поиска простых чисел, т.е. само решето Эратосфена

Для того чтобы просматривать массив и его индексы нам нужен цикл - делаем цикл (0 и 1 индексы мы не просматриваем). В этом цикле мы будем просматривать значения от 2 до значения корня из size. Почему так? Потому что, дойдя до корня из size, уже будут отсеяны все числа, не относящиеся простым. Поступая таким образом, мы уменьшаем количество итераций, а, соответственно, и нагрузку на процессор компьютера, что есть хорошо.

For(int i = 2; i < sqrt(size); i++) { }

Для "просева" на решете Эратосфена находится первый элемент массива с истинным значением. В самом начале работы программы этим элементом будет элемент с индексом 2. Далее выполняется условие if и мы попадаем на внутренний цикл for, который служит для просмотра остальной части массива (с 3 по 1000 индексы). Значение каждого индекса, а наши числа у нас выражены в индексах, будут проверяться на наличие остатка от деления на 2. Если число делится без остатка, значит, оно уже не может быть простым и значит, соответственно, выставляем эту ячейку в false. Смотрим код

For(int i = 2; i < sqrt(size); i++) { if(array[i] == true) { for(int j = i * 2; j < size; j++) { if(j % i == 0) array[j] = false; } } }

Для более наглядной демонстрации того, что произойдет после первой итерации, где i = 2 привожу рисунок для массива из 20 значений, по аналогии вы поймете, что происходит с нашим массивом из 1000 элементов.

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

Переходим на следующую итерацию, в которой i = 3. Выполняется условие if, т.к. 3 не было "просеяно" в предыдущей итерации, попадаем опять же на внутренний цикл, который обрабатывает оставшуюся часть массива (индексы от 4 до 1000).

Рисунок ниже иллюстрирует полученную картину


Как видите, были исключены все числа, кратные трем, не исключенные ранее "двойкой".

Переходим к следующей итерации, где i = 4. Здесь условие if не выполняется, поэтому "просеиваться" ничего не будет. Далее, следующая итерация с i = 5, здесь будут помечены в false значения массива с индексами кратными 5, которые не были помечены ранее по иным критериям: исключаются 25, 35, 45 и так далее. Следующими "рабочими" итерациями, в которых будут выполняться "просевы" являются итерации с i = 7, 11, 13, 17 и так далее, вплоть до корня из size (т.к. после него уже не может встретиться число, не относящееся к простому).

4. Завершающим этапом работы алгоритма "Решето Эратосфена", является печать результатов. Для вывода результатов воспользуемся таким циклом

For(int i = 2; i < mySize; i++) { if(myArray[i] == true) cout << i << endl; }

5. Итог работы:

Алгоритм поиска простых чисел - решето Эратосфена на С++. Первый способ

//Алгоритм поиска простых чисел - Решето Эратосфена #include //прототип функции void printarray(bool, const int); using namespace std; int main() { const int size = 1000; bool array; for(int k = 2; k < size; k++) array[k] = true; for(int i = 2; i < sqrt(size); i++) { if(array[i] == true) { for(int j = i * 2; j < size; j++) { if(j % i == 0) array[j] = false; } } } printarray(array, size); return 0; } //функция для вывода результатов работы void printarray(bool myArray, const int mySize) { int counter = 0; for(int i = 2; i < mySize; i++) { if(myArray[i] == true) { cout << i << endl; counter++; } } //выводим общее количество найденных простых чисел cout << endl << "Total: " << counter << endl; }

Результат работы программы: (было найдено 168 простых чисел)


6. В пятом пункте был изложен первый способ реализации алгоритма поиска простых чисел. Предлагаю вашему вниманию и второй способ, в котором массив будет содержать не логические значения (истина / ложь), а значения целых чисел, которые мы будем "просеивать" на решете Эратосфена. Т.е. принцип работы алгоритма тот же, только реализация несколько иная. Возможно, вам эта реализация понравится даже более предыдущей, смотрим код

Алгоритм поиска простых чисел - решето Эратосфена на С++. Второй способ

//Решето Эратосфена #include void simplePrint(int, const int); using namespace std; int main() { const int size = 100; int array; for(int k = 0; k < size; k++) array[k] = k; array = 0; for(int i = 2; i < sqrt(size); i++) { if(array[i] != 0) { for(int j = i * 2; j < size; j += i) { array[j] = 0; } } } simplePrint(array, size); return 0; } void simplePrint(int array, const int size) { for(int i = 0; i < size; i++) if(array[i] != 0) cout << array[i] << endl; }

В этой реализации мы также задаем массиву начальные значения, но уже не логические, а числовые (0, 1, 2, 3, 4, 5 ...). Эти числовые значения и будут теми числами, которые мы будем "просеивать" на решете Эратосфена. Задаем значения таким кодом

For(int k = 0; k < sqrt(size); k++) array[k] = k;

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

For(int i = 2; i < sqrt(size); i++) { if(array[i] != 0) { for(int j = i * 2; j < size; j += i) { array[j] = 0; } } }

Разберем первую итерацию: i = 2. Выполняется условие if, т.к. вторая ячейка у нас содержит значение 2, и мы переходим во внутренний цикл, который и будет "просеивать" числа. Рассмотрев код, мы видим, что меняются (помечаются) в ноль все значения массива, кратные двум (4, 6, 8, 10, 12 и так далее). В следующей итерации будет то же самое, но уже с шагом 3, помечаются в ноль значения (6, 9, 12, 15, 18 и так далее).

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

For(int i = 0; i < size; i++) if(array[i] != 0) cout << array[i] << endl;

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

//функция для вывода результатов работы void printarray(bool myArray, const int mySize) { int counter = 0; //подсчитываем количество найденных простых чисел for(int i = 2; i < mySize; i++) if(myArray[i] == true) counter++; //выводим общее количество найденных простых чисел cout << endl << "Total: " << counter << endl << endl; //динамически создаем массив нужного размера int *simple = new int; //заполняем созданный массив простыми числами for(int i = 2, k = 0; i < mySize; i++) if(myArray[i] == true) simple = i; //выводим содержимое на экран for(int i = 0; i < counter; i++) cout << simple[i] << endl; }

Объявляем счетчик counter, который будет считать количество найденных простых чисел. Затем, зная их количество, мы можем динамически создать массив и наполнить его простыми числами. В конце функции выводим его содержимое на экран, тем самым демонстрируя список найденных величин, присутствующих в интервале от 0 до 1000.

Итак, алгоритм поиска простых чисел мы рассмотрели, в частности для этого было использовано "решето Эратосфена". Все вопросы по алгоритму можно задать на форуме, либо в комментариях.

Алгоритм

Для нахождения всех простых чисел не больше заданного числа n , следуя методу Эратосфена, нужно выполнить следующие шаги:

Теперь все не зачеркнутые числа в списке - простые.

На практике, алгоритм можно несколько улучшить следующим образом. На шаге № 3, числа можно зачеркивать, начиная сразу с числа , потому что все составные числа меньше его уже будут зачеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда станет больше, чем .

Неограниченный, постепенный вариант

В этом варианте простые числа вычисляются последовательно, без ограничения сверху, как числа находящиеся в промежутках между составными числами, которые вычисляются для каждого простого числа p начиная с его квадрата, с шагом в p (или для нечетных простых чисел 2p ). Первое простое число 2 (среди возрастающих положит

Перебор делителей

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

Псевдокод

Вход : натуральное число n Пусть A - булевый массив, индексируемый числами от 2 до n , изначально заполненный значениями true . для i := 2, 3, 4, ..., пока i ^2 ≤ n : если A [i ] = true : для j := i ^2, i ^2 + i , i ^2 + 2i , ..., пока j ≤ n : если A [j ] = true : A [j ] := false Теперь все числа i , такие что A [i ] = true , являются простыми.

Пример для

Запишем натуральные числа начиная от 2 до 30 в ряд:

Первое число в списке, 2 - простое. Пройдём по ряду чисел, зачёркивая все числа кратные 2 (то есть каждое второе, начиная с 2 2 = 4 ):

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Следующее незачеркнутое число, 3 - простое. Пройдём по ряду чисел, зачёркивая все числа кратные 3 (то есть каждое третье, начиная с 3 2 = 9 ):

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Следующее незачеркнутое число, 5 - простое. Пройдём по ряду чисел, зачёркивая все числа кратные 5 (то есть каждое пятое, начиная с 5 2 = 25 ). И т. д.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF

Введение

Впервые о простых числах мы узнали в 6 классе на уроке математики, когда изучали тему «Простые и составные числа». Так же на форзаце учебника «Математика-6» имеется таблица простых чисел до числа 997 (Приложение 1 ). Мы знаем то, что находится на форзаце, имеет важную значимость в изучении данного предмета. И действительно, это подтвердилось при дальнейшем изучении математики

Мы заинтересовались происхождением простых чисел, алгоритмами нахождения простых чисел, алгоритмом создания таблиц простых чисел, в частности, «решетом Эратосфена».

Работу начали с анкетирования учащихся 6 - 10 классов нашей школы, чтобы выяснить знают ли они:

1. Что такое решето?

3. Кто такой Эратосфен?

В опросе приняли участие 90 человек. Результаты оказались следующими (Приложение 2).

Проанализировав ответы учащихся, мы убедились, что наша тема актуальна . Поэтому мы и решили глубже исследовать тему «Простые числа» и рассказать другим ученикам о простых числах на модели «решето Эратосфена».

Гипотеза : Действительно ли мы можем найти простое число больше 997.

Цель работы : изучить алгоритм построения «решета Эратосфена» и изготовить его материальную модель для использования на уроках математики.

Задачи:

1. Изучить имеющуюся литературу по теме проекта.

2 .Провести опрос по теме проекта.

3 .Найти простые числа, больше числа 997.

4. Изготовить материальную модель решета Эратосфена.

Объект исследования: простые числа, «решето Эратосфена»

Предмет исследования : таблица простых чисел

Методы исследования:

1.Работа с учебной и научно-популярной литературой, ресурсами сети Интернет.

2. Анкетирование,

3. Опыты и эксперименты с простыми числами

Этапы проекта:

Теоретический

Практический

2. Основная часть

2.1. Краткое описание используемых понятий

Решето - это утварь для просеивания муки, состоящая из широкого обруча и натянутой на него с одной стороны сетки. Решето отличается от сита более крупным размером отверстий сетки. (Толковый словарь Ушакова)

Решето -1) Предмет обихода широкий обруч с натянутой на него частой сеткой для просеивания чего-нибудь

2) Просеивающее устройство. (Толковый словарь Ожегова )

Решето - всякая несплошная вещь со сквозниной, с промежками, пролётами; ряд установленных жёрдочек, шестиков…переплетённых вдоль и поперёк, или иным образом. (Толковый словарь Даля )

Простое число - это натуральное число, которое не имеет других делителей кроме 1 и самого себя. (Пример: число 19 = 1 * 19)

Составное число - это натуральное число, у которого есть делители,отличные от 1 и самого себя. (Пример: число 10 = 5*2)

Всякое составное число можно разложить на простые множители.(Например: 63=3*3*7 или 363= 3*11*11)

Число 1 имеет только один делитель: само это число. Поэтому оно не относит ни к простым, ни к составным числам.

Первым проблему определения простых чисел обозначил и решил древнегреческий ученый Эратосфен Киренский примерно в 220 году до нашей эры, предложив один из алгоритмов определения простых чисел. Этот способ назвали «решето Эратосфена».

В 1909 году американский математик Деррик Норман Лемер опубликовал таблицы простых чисел в промежутке от 1 до 10.017.000. Книга таблиц имеется в Российской государственной библиотеке в Москве.

Еще более титаническую вычислительную работу выполнил профессор Парижского университета славянский математик Якуб Филипп Кулик (01.05.1793- 28.02.1863).Над своей рукописью «Великий канон делителей всех чисел, не делящихся на 2, 3 и 5, и заключенных между ними простых чисел до 100 300 201» он работал последние 20 лет жизни, не имея никакой надежды на его издание. Это произведение до сих пор не напечатано. Оно хранится в библиотеки Венской АкадемииНаук.

2.2. Биография Эратосфена

Вопросом изучения простых чисел, закономерности их появления и поиском самого большого простого числа математики занимаются очень давно. Первые сведения о простых числах, встречаются в трудах древне - греческого математика Эратосфена Киренского (276г.до н.э-194г. до н.э).

Греческий математик Эратосфен, живший более чем за 200 лет до н.э., составил первую таблицу простых чисел. Это один из самых разносторонних ученых античности. Особенно прославили Эратосфена труды по астрономии, географии и математике, однако он успешно трудился и в области филологии, поэзии, музыки и философии, за что современники дали ему прозвище Пентатл, т.е. Многоборец. Другое его прозвище Бета, т.е. «второй», возможно, также не содержит ничего уничижительного: им желали показать, что во всех науках Эратосфен достигает не высшего, но превосходного результата. Он первый вычислил окружность Земли, пользуясь методами геометрии.

Эратосфен родился в Африке, в Кирене. Учился сначала в Александрии, а затем в Афинах. Вероятно, именно благодаря столь широкому образованию и разнообразию интересов Эратосфен получил от Птолемея III приглашение вернуться в Александрию, чтобы стать воспитателем наследника престола и возглавить Александрийскую библиотеку (одну из первых библиотек в мире). В знаменитой библиотеке хранилось более 700 000 свитков, которые содержали все сведения о мире, известные людям той эпохи. Эратосфен принял это предложение и занимал должность библиотекаря вплоть до своей кончины. При содействии своих помощников Эратосфен первым рассортировал свитки по темам. Он дожил до глубокой старости, а когда ослеп, то перестал есть и умер от голода. Он не представлял себе жизни без возможности работать со своими любимыми книгами.

Его научные таланты удостоились высокой оценки современника Эратосфена, Архимеда, который посвятил ему свою книгу Эфодик (т.е. Метод)

2.3. Из истории появления «решета Эратосфена»

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

1 .Из ряда чисел: 2,3,4,5,6,7,8,9,10,11,12,13 и т. д вычёркиваем числа кратные 2.

2 .Затем, вычёркиваем числа кратные 3.

3 .Вычёркиваем числа кратные 4.

4 .Вычёркиваем числа кратные 5.

5 .Вычёркиваем числа кратные 6 .

6 .Делим, пока все составные числа не будут «просеяны», и останутся только простые числа: 2,5,7,11,.13….

Пример

Запишем натуральные числа, начиная от 2 до 20 в ряд.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Первое число в списке 2 — простое. Пройдём по ряду чисел, вычёркивая все числа кратные 2

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Следующее не вычеркнутое число 3 — простое. Пройдём по ряду чисел, вычёркивая все числа кратные 3

2 3 5 6 7 9 11 12 13 15 17 19

Процесс окончен. Все незачеркнутые числа последовательности являются простыми.

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

2.4. Практическая часть проекта: изготовление решета Эратосфена

Для изготовления «решета Эратосфена» мы взяли фанеру формата 36*42. Начертили сетку, в каждой клетке записали натуральные числа от 1001 до 1120.

Используя алгоритм построения «решета Эратосфена», проделали отверстия в тех клетках, в которых указаны составные числа.(Приложение 3)

    Заключение

Мы изучили алгоритм построения «решета Эратосфена», изготовили его материальную модель, изучили литературу и провели опрос. Подтвердили гипотезу, что можно найти простое число, больше чем 997.

Следовательно - наша цель достигнута, проблема решена. Разработанные нами материалы могут использоваться на уроках математики.

    Список использованной литературы

    Я познаю мир. Детская энциклопедия: Математика/ Я 11 Авт.-сост. А.П. Савин и др.: - М.: ООО «Издательство АСТ», 2001.

    Интернет - ресурсы(Википедия)

    А.Г. Мерзляк, В.Б. Полонский, М.С. Якир. Учебник «Математика 6 класс»:Издательство «Вентана-Граф», Москва, 2014

    Толковый словарь Ушакова

    Толковый словарь Ожегова

    Толковый словарь Даля

Приложение 1

таблица простых чисел

Приложение 2

Анкетирование

1. Что такое решето?

2. Какие числа называются простыми?

3. Кто такой Эратосфен?

4. Что такое «решето Эратосфена»?

В опросе приняли участие 90 человек. Результаты оказались следующими.

Вопрос

«да»

«нет»

Знаете ли вы что такое решето?

Знаете ли вы какие числа называются простыми?

Знаете ли вы кто такой Эратосфен?

Знаете ли вы что такое «решето Эратосфена»?

Приложение 3

модель решета Эратосфена


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

Навигация по странице.

Простые и составные числа – определения и примеры

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

Определение.

Простые числа – это целые числа, большие единицы, которые имеют только два положительных делителя, а именно самих себя и 1 .

Определение.

Составные числа – это целые числа, большие единицы, которое имеют, по крайней мере, три положительных делителя.

Отдельно заметим, что число 1 не относится ни к простым, ни к составным числам. Единица имеет только один положительный делитель, которым является само число 1 . Этим число 1 отличается от всех остальных целых положительных чисел, которые имеют не менее двух положительных делителей.

Учитывая, что целые положительные числа – это , и что единица имеет только один положительный делитель, можно привести другие формулировки озвученных определений простых и составных чисел.

Определение.

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

Определение.

Составными числами называют натуральные числа, имеющие более двух положительных делителей.

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

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

Определение.

Натуральные числа, которые не являются простыми, называются составными .

Приведем примеры простых и составных чисел .

В качестве примеров составных чисел приведем 6 , 63 , 121 и 6 697 . Это утверждение тоже нуждается в пояснении. Число 6 имеет кроме положительных делителей 1 и 6 еще и делители 2 и 3 , так как 6=2·3 , поэтому 6 – действительно составное число. Положительными делителями 63 являются числа 1 , 3 , 7 , 9 , 21 и 63 . Число 121 равно произведению 11·11 , поэтому его положительными делителями являются 1 , 11 и 121 . А число 6 697 составное, так как его положительными делителями кроме 1 и 6 697 являются еще и числа 37 и 181 .

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

Таблица простых чисел

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

Возникает логичный вопрос: «Почему мы заполнили таблицу простых чисел только до 1 000 , разве нельзя составить таблицу всех существующих простых чисел»?

Ответим сначала на первую часть этого вопроса. Для большинства задач, при решении которых придется использовать простые числа, нам будет вполне достаточно простых чисел в пределах тысячи. В остальных случаях, скорее всего, придется прибегать к каким-либо специальным приемам решения. Хотя, несомненно, мы можем составить таблицу простых чисел до сколь угодно большого конечного целого положительного числа, будь то 10 000 или 1 000 000 000 , в следующем пункте мы поговорим о методах составления таблиц простых чисел, в частности, разберем способ, получивший название .

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

Теорема.

Наименьший положительный и отличный от 1 делитель натурального числа, большего единицы, является простым числом.

Доказательство.

Пусть a – натуральное число, большее единицы, и b – наименьший положительный и отличный от единицы делитель числа a . Докажем, что b – простое число методом от противного.

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

Так как число a делится на b по условию, и мы сказали, что b делится на b 1 , то понятие делимости позволяет говорить о существовании таких целых чисел q и q 1 , что a=b·q и b=b 1 ·q 1 , откуда a= b 1 ·(q 1 ·q) . Из следует, что произведение двух целых чисел есть целое число, тогда равенство a=b 1 ·(q 1 ·q) указывает на то, что b 1 является делителем числа a . Учитывая полученные выше неравенства 1

Теперь мы можем доказать, что простых чисел бесконечно много.

Теорема.

Простых чисел бесконечно много.

Доказательство.

Предположим, что это не так. То есть, предположим, что простых чисел всего n штук, и эти простые числа есть p 1 , p 2 , …, p n . Покажем, что мы всегда можем найти простое число, отличное от указанных.

Рассмотрим число, p равное p 1 ·p 2 ·…·p n +1 . Понятно, что это число отлично от каждого из простых чисел p 1 , p 2 , …, p n . Если число p - простое, то теорема доказана. Если же это число составное, то в силу предыдущей теоремы существует простой делитель этого числа (обозначим его p n+1 ). Покажем, что этот делитель не совпадает ни с одним из чисел p 1 , p 2 , …, p n .

Если бы это было не так, то по свойствам делимости произведение p 1 ·p 2 ·…·p n делилось бы на p n+1 . Но на p n+1 делится и число p , равное сумме p 1 ·p 2 ·…·p n +1 . Отсюда следует, что на p n+1 должно делиться второе слагаемое этой суммы, которое равно единице, а это невозможно.

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

Итак, в силу того, что простых чисел бесконечно много, при составлении таблиц простых чисел всегда ограничивают себя сверху каким-либо числом, обычно, 100 , 1 000 , 10 000 и т.д.

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

Сейчас мы обсудим способы составления таблиц простых чисел. Предположим, что нам нужно составить таблицу простых чисел до 100 .

Самым очевидным методом решения этой задачи является последовательная проверка целых положительных чисел, начиная с 2 , и заканчивая 100 , на наличие положительного делителя, который больше 1 и меньше проверяемого числа (из свойств делимости мы знаем, что абсолютная величина делителя не превосходит абсолютной величины делимого, отличного от нуля). Если такой делитель не найден, то проверяемое число является простым, и оно заносится в таблицу простых чисел. Если же такой делитель найден, то проверяемое число является составным, оно НЕ заносится в таблицу простых чисел. После этого происходит переход к следующему числу, которое аналогично проверяется на наличие делителя.

Опишем несколько первых шагов.

Начинаем с числа 2 . Число 2 не имеет положительных делителей, кроме 1 и 2 . Следовательно, оно простое, поэтому, заносим его в таблицу простых чисел. Здесь следует сказать, что 2 является наименьшим простым числом. Переходим к числу 3 . Его возможным положительным делителем, отличным от 1 и 3 , является число 2 . Но 3 на 2 не делится, поэтому, 3 – простое число, и его также нужно занести в таблицу простых чисел. Переходим к числу 4 . Его положительными делителями, отличными от 1 и 4 , могут быть числа 2 и 3 , проверим их. Число 4 делится на 2 , поэтому, 4 – составное число, и его не нужно заносить в таблицу простых чисел. Обратим внимание на то, что 4 – наименьшее составное число. Переходим к числу 5 . Проверяем, являются ли его делителем хотя бы одно из чисел 2 , 3 , 4 . Так как 5 не делится ни на 2 , ни на 3 , ни на 4 , то оно простое, и его надо записать в таблицу простых чисел. Дальше происходит переход к числам 6 , 7 , и так далее до 100 .

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

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

Покажем решето Эратосфена в действии при составлении таблицы простых чисел до 50 .

Сначала записываем по порядку числа 2, 3, 4, …, 50 .


Первое записанное число 2 является простым. Теперь от числа 2 последовательно перемещаемся вправо на два числа и зачеркиваем эти числа, пока не доберемся до конца составляемой таблицы чисел. Так будут вычеркнуты все числа, кратные двум.

Первым следующим за 2 невычеркнутым числом является 3 . Это число простое. Теперь от числа 3 последовательно перемещаемся вправо на три числа (учитывая и уже зачеркнутые числа) и вычеркиваем их. Так будут вычеркнуты все числа, кратные трем.

Первым следующим за 3 невычеркнутым числом является 5 . Это число простое. Теперь от числа 5 последовательно перемещаемся вправо на 5 чисел (учитываем и зачеркнутые ранее числа) и вычеркиваем их. Так будут вычеркнуты все числа, кратные пяти.

Дальше вычеркиваем числа, кратные 7 , затем, кратные 11 и так далее. Процесс заканчивается, когда не останется чисел для вычеркивания. Ниже показана законченная таблица простых чисел до 50 , полученная с помощью решета Эратосфена. Все незачеркнутые числа являются простыми, а все зачеркнутые числа – составными.

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

Теорема.

Наименьший положительный и отличный от единицы делитель составного числа a не превосходит , где - из a .

Доказательство.

Обозначим буквой b наименьший и отличный от единицы делитель составного числа a (число b является простым, что следует из теоремы, доказанной в самом начале предыдущего пункта). Тогда существует такое целое число q , что a=b·q (здесь q – положительное целое число, что следует из правил умножения целых чисел), причем (при b>q нарушится условие, что b – наименьший делитель числа a , так как q также является делителем числа a в силу равенства a=q·b ). Умножив обе части неравенства на положительное и большее единицы целое число b (это нам позволяют сделать ), получаем , откуда и .

Что же нам дает доказанная теорема, касательно решета Эратосфена?

Во-первых, вычеркивание составных чисел, кратных простому числу b следует начинать с числа, равного (это следует из неравенства ). Например, вычеркивание чисел, кратных двум, следует начинать с числа 4 , кратных трем – с числа 9 , кратных пяти – с числа 25 , и так далее.

Во-вторых, составление таблицы простых чисел до числа n с помощью решета Эратосфена можно считать законченным тогда, когда будут вычеркнуты все составные числа, кратные простым числам, не превосходящим . В нашем примере n=50 (так как мы составляем таблицу простых чисел до 50 ) и , поэтому решето Эратосфена должно отсеять все составные числа, кратные простым числам 2 , 3 , 5 и 7 , которые не превосходят арифметического квадратного корня из 50 . То есть, нам дальше не нужно заниматься поиском и вычеркиванием чисел, кратных простым числам 11 , 13 , 17 , 19 , 23 и так далее до 47 , так как они уже будут вычеркнуты, как кратные меньшим простым числам 2 , 3 , 5 и 7 .

Данное число простое или составное?

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

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

Пример.

Докажите, что число 898 989 898 989 898 989 составное.

Решение.

Сумма цифр данного числа равна 9·8+9·9=9·17 . Так как число, равное 9·17 делится на 9 , то по признаку делимости на 9 можно утверждать, что исходное число также делится на 9 . Следовательно, оно составное.

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

Самый логичный подход состоит в переборе всех возможных делителей данного числа. Если ни один из возможных делителей не будет истинным делителем данного числа, то это число будет простым, в противном случае – составным. Из теорем, доказанных в предыдущем пункте, следует, что делители данного числа a нужно искать среди простых чисел, не превосходящих . Таким образом, данное число a можно последовательно делить на простые числа (которые удобно брать из таблицы простых чисел), пытаясь найти делитель числа a . Если будет найден делитель, то число a – составное. Если же среди простых чисел, не превосходящих , не окажется делителя числа a , то число a – простое.

Пример.

Число 11 723 простое или составное?

Решение.

Выясним, до какого простого числа могут быть делители числа 11 723 . Для этого оценим .

Достаточно очевидно, что , так как 200 2 =40 000 , а 11 723<40 000 (при необходимости смотрите статью сравнение чисел ). Таким образом, возможные простые делители числа 11 723 меньше числа 200 . Это уже значительно облегчает нашу задачу. Если бы мы этого не знали, то нам бы пришлось перебирать все простые числа не до 200 , а вплоть до числа 11 723 .

При желании можно оценить более точно. Так как 108 2 =11 664 , а 109 2 =11 881 , то 108 2 <11 723<109 2 , следовательно, . Таким образом, любое из простых чисел, меньших 109 , потенциально является простым делителем данного числа 11 723 .

Теперь мы будем последовательно делить число 11 723 на простые числа 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 , 101 , 103 , 107 . Если число 11 723 разделится нацело на одно из записанных простых чисел, то оно будет составным. Если же оно не делится ни на одно из записанных простых чисел, то исходное число простое.

Не будем описывать весь этот монотонный и однообразный процесс деления. Сразу скажем, что 11 723

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

Чтобы понять данный алгоритм, вспомним, что числа являются простыми, если делятся только на единицу и самих себя. Первое простое число - это 2, второе простое число - это 3. Теперь начнем рассуждать:

  1. Все четные числа, кроме двойки, - составные, т. е. не являются простыми, так как делятся не только на себя и единицу, а также еще на 2.
  2. Все числа кратные трем, кроме самой тройки, - составные, так как делятся не только на самих себя и единицу, а также еще на 3.
  3. Число 4 уже выбыло из игры, так как делится на 2.
  4. Число 5 простое, так как его не делит ни один простой делитель, стоящий до него.
  5. Если число не делится ни на одно простое число, стоящее до него, значит оно не будет делиться ни на одно сложное число, стоящее до него.

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

Алгоритм Эратосфена как раз заключается в последовательной проверке делимости чисел на предстоящие простые числа. Сначала берется первое простое и из ряда натуральных чисел высеиваются все кратные ему. Затем берется следующее простое и отсеиваются все кратные ему и так далее.

При реализации алгоритма Эратосфена на языке программирования есть некоторая сложность. Допустим, мы помещаем натуральные числа до заданного числа n в массив. Далее в процессе выполнения алгоритма будем заменять обнаруженные сложные числа нулями. После выполнения алгоритма те ячейки массива, которые не содержат нули, содержат простые числа, которые выводятся на экран.

Однако индексация массива начинается с нуля, а простые числа начинаются с двойки. Эта проблема решаема, но добавляет сложности в код. Поскольку алгоритм Эратосфена не такой уж простой, легче пренебречь началом и взять массив от 0 до n . Здесь важнее индексы, чем значения элементов. Значениями может быть True, обозначающее простое число, и False, обозначающее сложное число.

В данном примере реализации алгоритма Эратосфена список заполняется числами от 0 до n включительно так, что индексы элементов совпадают с их значениями. Далее все непростые числа заменяются нулями:

n = int (input () ) # список заполняется значениями от 0 до n a = for i in range (n + 1 ) : a.append (i) # Вторым элементом является единица, # которую не считают простым числом # забиваем ее нулем. a[ 1 ] = 0 # начинаем с 3-го элемента i = 2 while i <= n: # Если значение ячейки до этого не было обнулено, # в этой ячейке содержится простое число. if a[ i] != 0 : # первое кратное ему будет в два раза больше j = i + i while j <= n: # это число составное, поэтому заменяем его нулем a[ j] = 0 # переходим к следующему числу, которое кратно i (оно на i больше) j = j + i i += 1 # Превращая список во множество, # избавляемся от всех нулей кроме одного. a = set (a) # удаляем ноль a.remove (0 ) print (a)

Пример выполнения.