Эратосфен: биография и вклад в географию и математику

Содержание

• Слайд 1

  Стеценко Олеся
  6 «А»
  Решето Эратосфена

• Слайд 2

  Одной из самых больших загадок математики является расположение простых чисел в ряду всех натуральных чисел. Иногда два простых числа идут через одно, (например, 17 и 19, 29 и 31), а иногда подряд идет миллион составных чисел. Сейчас ученые знают уже довольно много о том, сколько простых чисел содержится среди N первых натуральных чисел. В этих подсчетах весьма полезным оказался метод, восходящий еще к древнегреческому ученому Эратосфену Киренскому. Он жил в третьем веке до новой эры в Александрии.

• Слайд 3

  (Eratosthenes, 276-194 г. до н. э.), греческий ученый, который первым вычислил окружность Земли, пользуясь методами геометрии. Он был чрезвычайно любознательным человеком. Прославился своими работами по математике, географии, философии и литературе. Заведовал Александрийской библиотекой в Египте (одной из первых библиотек в мире).

  ЭРАТОСФЕН

• Слайд 4

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

  Он дожил до глубокой старости. Когда он ослеп от старости, то перестал есть и умер от голода. Он не представлял себе жизни без возможности работать со своими любимыми книгами.

• Слайд 5

  В математике Эратосфена интересовал вопрос о том, как найти все простые числа среди натуральных чисел от 1 до .
  (Эратосфен считал 1 простым числом. Сейчас математики считают 1 числом особого вида, которое не относится ни к простым, ни к составным числам.)
  Эратосфен изобрел системный метод определения простых чисел путем отбора и отбрасывания чисел, имеющих делители, — все оставшиеся числа являются простыми. Этот метод впоследствии получил название решето Эратосфена и используется до сих пор, однако при работе с большими числами он неудобен, поскольку требуется слишком много времени, чтобы проверить наличие у них делителей.

• Слайд 6

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

• Слайд 7

  Просто́е число́ — это натуральное число, которое имеет ровно два натуральных делителя (только 1 и самого себя). Все остальные числа, кроме единицы, называются составными. Таким образом, все натуральные числа большие единицы разбиваются на простые и составные.
  Простое число

• Слайд 8

  Натуральное число

  Натура́льные чи́сла (естественные числа) — числа, возникающие естественным образом при счёте .
  Существуют два подхода к определению натуральных чисел — числа, используемые при:

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

  Отрицательные и нецелые числа натуральными числами не являются.

  ***
  Множество всех натуральных чисел принято обозначать знаком N. Множество натуральных чисел является бесконечным, так как для любого натурального числа найдётся большее его натуральное число.

• Слайд 9

  Составное число

  Составное число́ — натуральное число большее 1, не являющееся простым. Каждое составное число является произведением двух натуральных чисел, больших 1.

  ***
  Последовательность составных чисел начинается так:
  4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, …

• Слайд 10

  Как работать с Решетом Эратосфена?

  Итак, это алгоритм нахождения всех простых чисел не больше заданного числа N (пусть N=100)
  Следуя методу Эратосфена, нужно выполнить следующие шаги:
  Выписать подряд все натуральные числа от 2 до N (число 2 в списке-простое)

  Как работать с Решетом Эратосфена?

• Слайд 11

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

• Слайд 12

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

• Слайд 13

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

• Слайд 14

  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.

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

• Слайд 15

Посмотреть все слайды

Навигация

Вспомним географию

Варианты
expanded
collapsed

Ещё
expanded
collapsed

На других языках

• Afrikaans
• Alemannisch
• العربية
• مصرى
• Asturianu
• Azərbaycanca
• Беларуская
• Български
• भोजपुरी
• বাংলা
• བོད་ཡིག
• Brezhoneg
• Bosanski
• Català
• کوردی
• Čeština
• Cymraeg
• Dansk
• Deutsch
• ދިވެހިބަސް
• Ελληνικά
• English
• Esperanto
• Español
• Eesti
• Euskara
• فارسی
• Suomi
• Võro
• Français
• Gaeilge
• Galego
• עברית
• हिन्दी
• Hrvatski
• Magyar
• Հայերեն
• Bahasa Indonesia
• Íslenska
• Italiano
• 日本語
• ქართული
• Қазақша
• ಕನ್ನಡ
• 한국어
• Кыргызча
• Latina
• Ligure
• Lietuvių
• Latviešu
• Malagasy
• Македонски
• മലയാളം
• मराठी
• Bahasa Melayu
• မြန်မာဘာသာ
• Nederlands
• Norsk nynorsk
• Norsk bokmål
• Occitan
• Polski
• Piemontèis
• پنجابی
• Português
• Română
• Русиньскый
• Sicilianu
• Scots
• Srpskohrvatski / српскохрватски
• Simple English
• Slovenčina
• Slovenščina
• Shqip
• Српски / srpski
• Svenska
• Kiswahili
• தமிழ்
• ไทย
• Tagalog
• Türkçe
• Татарча/tatarça
• Українська
• اردو
• Oʻzbekcha/ўзбекча
• Tiếng Việt
• West-Vlams
• Winaray
• 吴语
• 中文
• 粵語

биография

Первые годы

Эратосфен родился примерно в 276 г. до н.э. в Кирене, греческом городе, расположенном в Северной Африке, на территории, которая сейчас является территорией Ливии

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

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

Кирена была поглощена Птолемейской монархией Египта, которая управляла Александрией, культурным и торговым центром Средиземноморья. Был большой книжный магазин, музей и школа повышения квалификации.

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

Дети с семи лет обучались таким предметам, как литература, спорт и музыка. Считается, что Эратосфен также мог быть учеником Каллимах.

Афины

Основным интересом Эратосфена к юности была философия, и это призвание привело его в Афины в возрасте 15 лет. Там он оставался примерно 25 лет. Затем он подготовил и приобрел известность как академический.

В Афинах он нашел так много философов, что он был поражен и поражен. Сначала он учился у Зенона в школе стоиков. Также с одним из его учеников, Аристоном де Хиосом, из которого он написал биографию. Но он не нашел в них стиля, который ему нравился.

Затем он присоединился к платоникам как ученик Арцесилао. Именно тогда Эратосфен создал произведение под названием Platonicus, в которой, следуя методу Платона, он исследовал математические и космологические темы. В то время он также написал Пери Агатōн кай какōN, текст, который был потерян.

После этих переживаний он разочаровался в философии и решил посвятить себя поэзии. Так началась слава Эратосфена, так как в своей новой области он добился признания, которого хотел.

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

Александрия

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

Город Кирена прошел независимый период Египта до брака между Птоломео III и Беренис, дочерью Магаса, губернатора этого города

Птолемей III был тронут не только интересом к работе Эратосфена, но и политическими соображениями. Город Кирена прошел независимый период Египта до брака между Птоломео III и Беренис, дочерью Магаса, губернатора этого города.

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

В период, когда Эратосфен руководил Александрийской библиотекой, в ней были достигнуты большие успехи. Приобретенные произведения, такие как великие драмы Эсхила и Еврипида. Они также расширили исследования в Софокла.

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

смерть

Эратосфен умер в Александрии, около 194 г. до н.э., когда ему было 82 года. Некоторое время назад он ослеп в результате катаракты и, как полагают, совершил самоубийство от голода.

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

Тем не менее, его вклад в изучение земли дал ему титул отца географии. В течение своей жизни Эратосфен был любителем знаний во всех областях.

Биография великого математика Эратосфен Киренский

Литература[править | править код]

• Античная география. М., 1953.
• Бобынин В. В. Эратосфен // Энциклопедический словарь Брокгауза и Ефрона : в 86 т. (82 т. и 4 доп.). — СПб., 1890—1907.
• Дитмар А.Б. Родосская параллель: Жизнь и деятельность Эратосфена. — М.: Мысль, 1965. — 72 с.
• Колчинский И.Г., Корсунь А.А., Родригес М.Г. Астрономы: Биографический справочник. — 2-е изд., перераб. и доп. — Киев: Наукова думка, 1986. — 512 с.

На иностранных языках

• Aujac G. Eratosthène de Cyrène, le pionier de la geographie. — Paris: Édition du CTHS, 2001. — 224p.
• Diller A. Geographical Latitudes in Eratosthenes, Hipparchus and Posidonius // Klio. — 1934. — Bd. 27. — Heft 3. — S. 258—269.
• Dutka J. Eratosthenes’ measurement of the Earth reconsidered. Archive for History of Exact Sciences, 46, 1993, p. 55-64.
• Fraser P. M. Ptolemaic Alexandria. — Oxford: Clarendon Press, 1972.
• Goldstein B. R. Eratosthenes on the measurement of the Earth // Historia Mathematica. — Vol. 11. — 1984. — P. 411—416.
• Rawlins D. Eratosthenes’ geodesy unraveled: was there a high-accuracy Hellenistic astronomy, Isis, 73, 1982, p. 259—265.
• Rawlins D. The Eratosthenes — Strabo Nile map. Is it the earliest surviving instance of spherical cartography? Did it supply the 5000 stades arc for Eratosthenes’ experiment?, Arch. Hist. Exact Sci, 26 (3), 1982, p. 211—219.
• Rawlins D. Eratothenes’s large earth and tiny universe. DIO, 14, 2008.
• Shcheglov D. A. Ptolemy’s System of Seven Climata and Eratosthenes’ Geography // Geographia Antiqua. — Vol. 13. — 2004 (2006). — P. 21-37.
• Thalamas A. La géographe d’Ératosthène. — Versailles, 1921.
• Wolfer E. P. Eratosthenes von Kyrene als Mathematiker und Philosoph. — Groningen-Djakarta, 1954.

Поиски длины экватора

Одной из задач, которая в особенности интересовала древнегреческого мастера географии, был вопрос поиска длины окружности Земли. За основу своей теории, приведшей к удивительным для того времени результатам, исследователь взял то, что города Александрия и Сиена (ныне Асуан) расположены на одном и том же меридиане. Киренский ученый наблюдал за отношением угла падения лучей, отбрасываемых небесным светилом в день летнего солнцестояния в двух этих населенных пунктах, к поверхности земли.

В своем исследовании математик и географ пользовался гномоном — специальным устройством, изобретенным другим древнегреческим ученым Анаксимандром Милетским и позволяющим с высокой точностью определить момент астрономического полдня.

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

Соотнеся полученное расстояние и значение угла 1 к 50, определенное при помощи гномона, древний математик и географ смог совершить прорыв, узнав примерную длину экватора Земли, которая, согласно его подсчетам, составила около 39250 км. Согласно современным высокоточным измерениям, длина экватора равняется 40120 км.

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

Ерте жылдар

Эратосфен шамамен б.з.д 276 жылы дүниеге келген. қазіргі Ливия жерінде Солтүстік Африкада орналасқан грек қаласы Киренада. Ол Аглаустың ұлы болған, ол туралы тарихи деректер сақталмаған, сондықтан ол сол кезде маңызды отбасының адамы емес деп ойлаған.

Атақты ата-тегіне ие болмаса да, Эратосфен осы қалада туып-өскен ер адамдар мойындаған қаладан шыққан. Сиренаны біздің заманымыздан бұрынғы 600 жылға дейін Терадан гректер құрды және ол эллин дәуірі келгенге дейін тәуелсіз қала ретінде өркендеді.

Кирен Жерорта теңізінің мәдени және сауда орталығы Александриядан басқарған Египеттің Птолемей монархиясына сіңіп кетті. Мұнда керемет кітап дүкені, мұражай және озық зерттеулер мектебі болды.

Эратосфен өз қаласындағы басқа академиктердің жолын қуып, грамматиканың білгірі Лисаниямен бірге оқыды. Грек заманында ауқатты отбасылардың жастары білім алуға көбірек мүмкіндік алғанына қарамастан, ерлер академиялары болды.

Балалар әдебиет, спорт және музыка сияқты пәндерге жеті жасынан бастап жаттығады. Эратосфен де Каллимахтың шәкірті болуы мүмкін деген болжам бар.

Различные оптимизации решета Эратосфена

Самый большой недостаток алгоритма — то, что он «гуляет» по памяти, постоянно выходя за пределы кэш-памяти, из-за чего константа, скрытая в , сравнительно велика.

Кроме того, для достаточно больших узким местом становится объём потребляемой памяти.

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

Просеивание простыми до корня

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

Таким образом, изменится внешний цикл алгоритма:

for (int i=2; i*i<=n; ++i)

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

Решето только по нечётным числам

Поскольку все чётные числа, кроме , — составные, то можно вообще не обрабатывать никак чётные числа, а оперировать только нечётными числами.

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

Уменьшение объёма потребляемой памяти

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

Однако такой подход — «битовое сжатие» — существенно усложнит оперирование этими битами. Любое чтение или запись бита будут представлять из себя несколько арифметических операций, что в итоге приведёт к замедлению алгоритма.

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

В завершение стоит отметить, что в языке C++ уже реализованы контейнеры, автоматически осуществляющие битовое сжатие: vector<bool> и bitset<>. Впрочем, если скорость работы очень важна, то лучше реализовать битовое сжатие вручную, с помощью битовых операций — на сегодняшний день компиляторы всё же не в состоянии генерировать достаточно быстрый код.

Блочное решето

Из оптимизации «просеивание простыми до корня» следует, что нет необходимости хранить всё время весь массив . Для выполнения просеивания достаточно хранить только простые до корня из , т.е. , а остальную часть массива строить поблочно, храня в текущий момент времени только один блок.

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

Приведём реализацию блочного решета. Программа считывает число и находит количество простых от до :

const int SQRT_MAXN = 100000; // корень из максимального значения N
const int S = 10000;
bool nprimeSQRT_MAXN, blS;
int primesSQRT_MAXN, cnt;
 
int main() {
 
	int n;
	cin >> n;
	int nsqrt = (int) sqrt (n + );
	for (int i=2; i<=nsqrt; ++i)
		if (!nprimei) {
			primescnt++ = i;
			if (i * 1ll * i <= nsqrt)
				for (int j=i*i; j<=nsqrt; j+=i)
					nprimej = true;
		}
 
	int result = ;
	for (int k=, maxk=nS; k<=maxk; ++k) {
		memset (bl, , sizeof bl);
		int start = k * S;
		for (int i=; i<cnt; ++i) {
			int start_idx = (start + primesi - 1)  primesi;
			int j = max(start_idx,2) * primesi - start;
			for (; j<S; j+=primesi)
				blj = true;
		}
		if (k == )
			bl = bl1 = true;
		for (int i=; i<S && start+i<=n; ++i)
			if (!bli)
				++result;
	}
	cout << result;
 
}

Асимптотика блочного решета такая же, как и обычного решета Эратосфена (если, конечно, размер блоков не будет совсем маленьким), зато объём используемой памяти сократится до и уменьшится «блуждание» по памяти. Но, с другой стороны, для каждого блока для каждого простого из будет выполняться деление, что будет сильно сказываться при меньших размерах блока. Следовательно, при выборе константы необходимо соблюсти баланс.

Как показывают эксперименты, наилучшая скорость работы достигается, когда имеет значение приблизительно от до .

Улучшение до линейного времени работы

Алгоритм Эратосфена можно преобразовать в другой алгоритм, который уже будет работать за линейное время — см. статью «Решето Эратосфена с линейным временем работы». (Впрочем, этот алгоритм имеет и недостатки.)

Асимптотика

Докажем, что асимптотика алгоритма равна .

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

Вспомним здесь два известных факта: что число простых, меньше либо равных , приблизительно равно , и что -ое простое число приблизительно равно (это следует из первого утверждения). Тогда сумму можно записать таким образом:

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

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

Первообразная для подынтегральной функции есть . Выполняя подстановку и убирая члены меньшего порядка, получаем:

Теперь, возвращаясь к первоначальной сумме, получаем её приближённую оценку:

что и требовалось доказать.

Более строгое доказательство (и дающее более точную оценку с точностью до константных множителей) можно найти в книге Hardy и Wright «An Introduction to the Theory of Numbers» (стр. 349).

Реализация

Сразу приведём реализацию алгоритма:

int n;
vector<char> prime (n+1, true);
prime = prime1 = false;
for (int i=2; i<=n; ++i)
	if (primei)
		if (i * 1ll * i <= n)
			for (int j=i*i; j<=n; j+=i)
				primej = false;

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

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

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