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

в этом видео мы рассмотрим древний способ нахождения всех простых чисел до некого предела н он называется решето эратосфена эратосфен родился в двести семьдесят шестом году до нашей эры то есть этому методу свыше 2200 лет но он очень простой и изящный его поймет даже ребенок пусть для примера нам нужно найти все простые числа до сотни точно по такому же принципу будут считаться числа до 10000 или до миллиарда алгоритм следующий изначально все числа у нас без пометок то есть на сером фоне начнем сначала если встречаем число без пометок значит оно простое так у нас здесь два оно простое и в его квадратики нет никаких пометок а на следующем шаге мы исключаем все числа кратные двойки потому что они составные давайте отметим их красным теперь опять повторяем алгоритм переходим от двойки-тройки тройка без пометок а это значит что она тоже простая а дальше исключаем все числа кратные трём можно оптимизировать алгоритм шестерка уже отмечено у нас мы можем начать закрашивать начиная с квадрата этого числа трижды 39 и мы помечаем все кратные тройки числа начиная с 9 как составные а дальше опять же переходим четверки четверка уже отмечено как составная значит переходим к пятерке и это у нас простое число пятью 525 отмечаем 25 30 35 40 45 и так далее это все составные числа идем дальше встречаем 77 не отмечено значит это простое число 7-ю 749 помечаем 49 и все кратные семи числа большее 49 дальше мы двигаемся и встречаем 1111 простое а дальше обратите внимание 11 на 11 это больше ста значит можно остановиться мы могли остановиться даже на 10 потому что к этому моменту все не отмеченные числа простые и в этом заключается весь алгоритм все очень просто давайте обобщим что у нас получилось чтобы можно было написать программу и так мы хотим найти все числа до некого н мы создаем главный цикл цикл по всем числом а от 2 до корня из n если помните мы остановились на 11 но можно было остановиться и на 10 к тому времени мы все простые числа нашли а в цикле у нас а вот что если число а не отмечено значит а простое в таком случае отмечаем все числа кратные а как составные затем возвращаемся назад увеличиваем а на единицу было два стола три затем 4 5 и так далее и в конце у нас останутся все простые числа обратите внимание что здесь еще один цикл у нас есть главный цикл по а а когда находим простое то отмечаем кратные внутри еще одного цикла важно понять у нас здесь вложенный цикл один цикл внутри другого вот пример этого алгоритма в действие можете посмотреть программу по ссылке в описании если вести 100 вот вам все простые до сотни если вести 200 вот все простые до 200 спасибо что подписывайтесь на наш канал мы будем рады услышать ваше мнение по поводу этого видео если у вас возникли вопросы касательно данного видеоролика то напишите их в комментариях и мы с удовольствием постараемся ответить на них