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

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

Гре­че­ский учё­ный Эра­то­сфен в III веке до н. э. при­думал спо­соб, алго­ритм нахож­де­ния всех про­стых чисел, не пре­вос­хо­дящих неко­то­рого фик­си­ро­ван­ного числа $N$. Выпишем все нату­раль­ные числа от $2$ до $N$. Вычерк­нем в списке все числа, крат­ные $2$ (кроме самой двойки); наименьшее невы­черк­ну­тое число после $2$ — это $3$, сле­дующее про­стое число. Остав­ляем тройку и вычёр­ки­ваем числа, крат­ные $3$, и т. д. Если такие действия про­де­лать для всех чисел, не пре­вос­хо­дящих $\sqrt{N}$, то неза­чёрк­ну­тыми оста­нутся все про­стые числа и только они.

Опи­сан­ный процесс можно меха­ни­зи­ро­вать, сде­лать нагляд­ным. Напе­ча­тайте на листе бумаги числа от $1$ до $N=nm$ в виде таб­лицы размера $n\times m$. На пер­вой про­зрачке на местах чёт­ных чисел (кроме $2$) напе­ча­тайте закрашен­ные обла­сти. На вто­рой — то же с чис­лами, крат­ными $3$ (кроме самой тройки), и т. д. Если создать доста­точно большой набор таких про­зра­чек, то при наложе­нии их на основ­ную таб­лицу все про­стые числа будут видны (прой­дут через сито, решето отбора), а все состав­ные — скрыты.

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

Решето Эра­то­сфена можно реа­ли­зо­вать раз­лич­ными спо­со­бами, в том числе и «меха­ни­че­ски». Одну идею под­ска­зы­вает само назва­ние: листы-под­ложки под­держи­вают шары, а вынима­ние оче­ред­ного листа при­во­дит к паде­нию шаров, «крат­ных» соот­вет­ствующему числу.

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

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