Таблицы Брадиса

Какие числа останутся на доске?

Какие числа останутся на доске?

Элементы математики в задачах - Г. А. Мерзон

Задача 13 (решето Эратосфена). На доске написаны все числа от

2  до 1000. Эратосфен обводит число 2 в кружочек и стирает все числа, отличные от 2, которые делятся на 2. Затем он повторяет этот процесс, а именно обводит в кружочек наименьшее необведенное число и стирает все остальные числа, которые делятся на это число. Процесс заканчивается, когда на доске остаются только обведенные числа. Какие числа останутся на доске? (Их не нужно выписывать.)

Ответ. На доске останутся только простые числа.

Ш Решето Эратосфена — древний способ выписывания подряд про­стых чисел. Задача построения простых чисел, с одной стороны, интересовала людей еще с древности как теоретическая задача, а с другой стороны, в последнее время в связи с задачами криптографии

158                  Целые числа 1 Делимость целых чисел

она приобрела и практическую ценность. Но существенно лучших алгоритмов перечисления простых чисел до сих пор не придумано.

Задача 14. Выпишите все простые числа, меньшие 100.

Решение.

99 100

 

 

 

 

 

43 44

 

39 40

 

 

 

 

 

©

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

©©

 

 

 

 

 

 

©@

©

 

 

@ @ ® ©© © ©

Задача 15. Докажите, что число а — составное, если и только если а делится на какое-нибудь простое число, не превосходящее -/а.