Алгоритм нахождения простых чисел — страница 2

  • Просмотров 2755
  • Скачиваний 65
  • Размер файла 22
    Кб

учителем Эратосфена в Александрии был философ Лизний. Перебравшись затем в Афины, он так тесно сблизился со школой Платона, что обыкновенно называл себя платоником. Результатом изучения наук в этих двух центрах была энциклопедическая эрудиция Эратосфена; кроме сочинений по математическим наукам, он писал ещё трактаты «О добре и зле», о комедии и др. Из всех своих сочинений Эратосфен придавал особенное значение чисто

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

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

нахождения всех простых чисел до некоторого целого числа n, который приписывают древнегреческому математику Эратосфену Киренскому Алгоритм Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги: Выписать подряд все целые числа от 2 до n (2,3,4…,n) Пусть переменная p изначально равна 2-первому простому числу. Вычеркнуть из списка все числа от 2p до n, делящиеся на p (то

есть, числа 2p,3p,4p,… .) Найти первое невычеркнутое число, большее, чем р, и присвоить значению переменной p это число. Повторять шаги 3 и 4 до тех пор, пока p не станет больше, чем n. Все невычеркнутые числа в списке - простые числа. На практике, алгоритм можно немного улучшить следующим образом. На шаге №3, числа можно вычеркивать, начиная сразу с числа p2, потому что все составные числа меньше его уже будут вычеркнуты к этому времени. И,

соответственно, останавливать алгоритм можно, когда p2 станет больше, чем n. Делимость чисел Признаки делимости Число делится на 2 тогда и только тогда когда оно заканчивается чётной цифрой или нулём. Число делится на 3, когда сумма цифр числа делится на 3. Число делится на 4 тогда и только тогда, когда число из двух его последних цифр (оно может быть двузначным, однозначным или нулём) делится на 4. Чтобы узнать, делится ли двузначное