Решето Эратосфена
Решето́ Эратосфе́на — алгоритм нахождения всех простых чисел до некоторого целого числа n, который приписывают древнегреческому математику Эратосфену Киренскому[1]. Как и во многих случаях, здесь название алгоритма говорит о принципе его работы, то есть решето подразумевает фильтрацию, в данном случае фильтрацию всех чисел за исключением простых. По мере прохождения списка нужные числа остаются, а ненужные (они называются составными) исключаются.
Содержание
История
Название «решето» метод получил потому, что, согласно легенде, Эратосфен писал числа на дощечке, покрытой воском, и прокалывал дырочки в тех местах, где были написаны составные числа. Поэтому дощечка являлась неким подобием решета, через которое «просеивались» все составные числа, а оставались только числа простые. Эратосфен дал таблицу простых чисел до 1000.
Алгоритм
Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:
- Выписать подряд все целые числа от двух до n (2, 3, 4, …, n).
- Пусть переменная p изначально равна двум — первому простому числу.
- Зачеркнуть в списке числа от 2p до n считая шагами по p (это будут числа кратные p: 2p, 3p, 4p, …).
- Найти первое незачёркнутое число в списке, большее чем p, и присвоить значению переменной p это число.
- Повторять шаги 3 и 4, пока возможно.
Теперь все незачёркнутые числа в списке — это все простые числа от 2 до n.
На практике, алгоритм можно улучшить следующим образом. На шаге № 3 числа можно зачеркивать начиная сразу с числа p2, потому что все составные числа меньше него уже будут зачеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда p2 станет больше, чем n.[2] Также, все простые числа (кроме 2) — нечётные числа, и поэтому для них можно считать шагами по 2p, начиная с p2.
Сложность алгоритма
Сложность алгоритма составляет <math>O(n \log (\log n))</math> операций при составлении таблицы простых чисел до <math>n</math>[3].
Доказательство сложности
При выбранном <math>n \in \mathbb{N}</math> для каждого простого <math>p \in \mathbb{P}\colon p \le n</math> будет выполняться внутренний цикл, который совершит <math>\frac{n}{p}</math> действий. Следовательно, нужно оценить следующую величину:
<math> \sum\limits_{p\in \mathbb{P}\colon p \le n} {\frac{n}{p}} = n\cdot\sum\limits_{p\in \mathbb{P}\colon p \le n} {\frac{1}{p}} </math>
Так как количество простых чисел, меньших либо равных <math>n</math>, оценивается как <math>\frac{n}{\ln n}</math>, и, как следствие, <math>k</math>-е простое число примерно равно <math>k\ln k</math>, то сумму можно преобразовать:
<math> \sum\limits_{p \in \mathbb{P}\colon p \le n}\frac{1}{p}\approx \frac{1}{2} + \sum\limits_{k=2}^{\frac{n}{\ln n}}\frac{1}{k\ln k}</math>
Здесь из суммы выделено слагаемое для первого простого числа, чтобы избежать деления на нуль. Теперь следует оценить эту сумму интегралом:
<math> \frac{1}{2} + \sum^{\frac{n}{\ln n}}_{k=2}{\frac{1}{k\ln k}} \approx \int\limits_2^{\frac{n}{\ln n}} {\frac{1}{k\ln k}}\,dk = \ln \ln k \Bigr|_2^{\frac{n}{\ln n}} = \ln \ln {\frac{n}{\ln n}} - \ln \ln 2 = \ln (\ln n - \ln \ln n) - \ln \ln 2 \approx \ln \ln n </math>
В итоге получается для изначальной суммы:
<math> \sum\limits_{p\in \mathbb{P}\colon p \le n} {\frac{n}{p}} \approx n \ln \ln n + o(n)</math>
Более строгое доказательство (и дающее более точную оценку с точностью до константных множителей) можно найти в книге Hardy и Wright «An Introduction to the Theory of Numbers»[4].
Псевдокод
Оптимизированная реализация (начинающаяся с квадратов) на псевдокоде[5][6]:
Вход: натуральное число n Пусть A — булевый массив, индексируемый числами от 2 до n, изначально заполненный значениями true. для i := 2, 3, 4, ..., пока i2 ≤ n: если A[i] = true: для j := i2, i2 + i, i2 + 2i, ..., пока j ≤ n: A[j] := false Выход: числа i, для которых A[i] = true.
Пример для n = 30
Запишем натуральные числа начиная от 2 до 30 в ряд:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Первое число в списке, 2 — простое. Пройдём по ряду чисел, зачёркивая все числа кратные 2 (то есть каждое второе, начиная с 22 = 4):
2 3456789101112131415161718192021222324252627282930
Следующее незачеркнутое число, 3 — простое. Пройдём по ряду чисел, зачёркивая все числа кратные 3 (то есть каждое третье, начиная с 32 = 9):
2 3456789101112131415161718192021222324252627282930
Следующее незачеркнутое число, 5 — простое. Пройдём по ряду чисел, зачёркивая все числа кратные 5 (то есть каждое пятое, начиная с 52 = 25). И т. д.
2 3456789101112131415161718192021222324252627282930
Следующее незачеркнутое число — 7. Его квадрат, 49 — больше 30-ти, поэтому на этом работа завершена. Все составные числа уже зачеркнуты:
2 3 5 7 11 13 17 19 23 29
Модификации метода
Неограниченный, постепенный вариант
В этом варианте простые числа вычисляются последовательно, без ограничения сверху, как числа находящиеся в промежутках между составными числами, которые вычисляются для каждого простого числа p, начиная с его квадрата, с шагом в p (или для нечетных простых чисел 2p)[2]. Может быть представлен символически в парадигме потоков данных как
primes = [2..] \ [[p*p, p*p+p..] for p in primes]
используя нотацию абстракции списков, где \ обозначает разницу между арифметическими прогрессиями.
Первое простое число 2 (среди возрастающих положительных целых чисел) заранее известно, поэтому в этом самореферентном определении нет порочного круга.
Перебор делителей
Решето Эратосфена часто путают с алгоритмами, которые отфильтровывают из заданного интервала составные числа, тестируя каждое из чисел-кандидатов с помощью перебора делителей.[7]
Широко известный функциональный код Дэвида Тёрнера 1975 года[8] часто принимают за решето Эратосфена,[7] но на самом деле это далёкий от оптимального вариант с перебором делителей.
Решето Эйлера
Решето Эйлера это вариант решета Эратосфена, в котором каждое составное число удаляется из списка только один раз.
Составляется исходный список начиная с числа 2. На каждом этапе алгоритма первый номер в списке берется как следующее простое число, и определяются его произведения на каждое число в списке которые маркируются для последуюшего удаления. После этого из списка убирают первое число и все помеченные числа, и процесс повторяется вновь:
[2] (3) 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 ... [3] (5) 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 ... [4] (7) 11 13 17 19 23 29 31 37 41 43 47 49 53 59 61 67 71 73 77 79 ... [5] (11) 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 ... [...]
Здесь показан пример начиная с нечетных чисел, после первого этапа алгоритма. Таким образом, после k-го этапа рабочий список содержит только числа взаимно простые с первыми k простыми числами (то есть числа не кратные ни одному из первых k простых чисел), и начинается с (k+1)-го простого числа. Все числа в списке, меньшие квадрата его первого числа, являются простыми.
Решето только по нечётным числам
Поскольку все чётные числа, кроме 2, — составные, то можно вообще не обрабатывать никак чётные числа, а оперировать только нечётными числами. Во-первых, это позволит вдвое сократить объём требуемой памяти. Во-вторых, это уменьшит количество выполняемых алгоритмом операций (примерно вдвое).
Это можно обобщить на числа взаимно простые не только с 2 (то есть нечетные числа), но и с 3, 5, и т. д.
Уменьшение объёма потребляемой памяти
Алгоритм Эратосфена фактически оперирует с <math>n</math> битами памяти. Следовательно, можно существенно сэкономить потребление памяти, храня <math>n</math> переменных булевского типа не как <math>n</math> байт, а как <math>n</math> бит, то есть <math>n/8</math> байт памяти.
Такой подход — «битовое сжатие» — усложняет оперирование этими битами. Любое чтение или запись бита будут представлять собой несколько арифметических операций. Но с другой стороны существенно улучшается компактность в памяти. Бо́льшие интервалы умещаются в кэш-память которая работает гораздо быстрее обычной так что при работе по-сегментно общая скорость увеличивается.
Решето Эратосфена с линейным временем работы
Этот алгоритм обнаруживает для каждого числа i в отрезке [2...n] его минимальный простой делитель lp[i].
Также поддерживается список всех простых чисел — массив pr[], поначалу пустой. В ходе работы алгоритма этот массив будет постепенно заполняться.
Изначально все величины lp[i] заполним нулями.
Дальше следует перебрать текущее число i от 2 до n. Здесь может быть два случая:
- lp[i] = 0: это означает, что число i — простое, так как для него так и не обнаружилось других делителей.
Следовательно, надо присвоить lp[i] = i и добавить i в конец списка pr[].
- lp[i] ≠ 0: это означает, что текущее число i — составное, и его минимальным простым делителем является lp[i].
В обоих случаях дальше начинается процесс расстановки значений в массиве lp[i]: следует брать числа, кратные i, и обновлять у них значение lp[]. Однако основная цель — научиться делать это таким образом, чтобы в итоге у каждого числа значение lp[] было бы установлено не более одного раза.
Утверждается, что для этого можно поступить таким образом. Рассматриваются числа вида x = p ⋅ i, где p последовательно равно всем простым числам не превосходящим lp[i] (как раз для этого понадобилось хранить список всех простых чисел).
У всех чисел такого вида проставим новое значение lp[x] — оно должно быть равно p[9].
Псевдокод
Вход: натуральное число n
Пусть pr - целочисленный массив, поначалу пустой;
lp - целочисленный массив, индексируемый от 2 до n, заполненный нулями
для i := 2, 3, 4, ..., до n:
если lp[i] = 0:
lp[i] := i
pr[] += {i}
для p из pr пока p ≤ lp[i] и p*i ≤ n:
lp[p*i] := p
Выход: все числа в массиве pr.
См. также
Напишите отзыв о статье "Решето Эратосфена"
Примечания
- ↑ Никомах Герасский, Введение в арифметику, I, 13. [www.archive.org/stream/nicomachigerasen00nicouoft#page/29/mode/1up]
- ↑ 1 2 Horsley, Rev. Samuel, F. R. S., "Κόσκινον Ερατοσθένους or, The Sieve of Eratosthenes. Being an Account of His Method of Finding All the Prime Numbers, " [www.jstor.org/stable/106053 Philosophical Transactions (1683—1775), Vol. 62. (1772), pp. 327—347].
- ↑ [habrahabr.ru/post/91112/ Волшебное решето Эратосфена]
- ↑ [archive.org/stream/AnIntroductionToTheTheoryOfNumbers-4thEd-G.h.HardyE.m.Wright#page/n363/mode/2up Hardy and Wright "An Introduction to the Theory of Numbers, p. 349]
- ↑ Algorithms in C++. — Addison-Wesley, 1992. — ISBN 0-201-51059-6., p. 16.
- ↑ Jonathan Sorenson, An Introduction to Prime Number Sieves, Computer Sciences Technical Report #909, Department of Computer Sciences University of Wisconsin-Madison, January 2 1990 (the use of optimization of starting from squares, and thus using only the numbers whose square is below the upper limit, is shown).
- ↑ 1 2 Colin Runciman, [portal.acm.org/citation.cfm?id=969898 «FUNCTIONAL PEARL: Lazy wheel sieves and spirals of primes»], Journal of Functional Programming, Volume 7 Issue 2, March 1997; также [citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.7096&rank=3 здесь].
- ↑ Turner, David A. SASL language manual. Tech. rept. CS/75/1. Department of Computational Science, University of St. Andrews 1975. (
sieve (p:xs) = p:sieve [x | x <- xs, rem x p > 0]; primes = sieve [2..]) - ↑ David Gries, Jayadev Misra. A Linear Sieve Algorithm for Finding Prime Numbers [1978]
Литература
- Гальперин Г. [kvant.mccme.ru/1987/04/prosto_o_prostyh_chislah.htm «Просто о простых числах»] // Квант. — № 4.
- Под. ред. Невская И.И. [lib.mipt.ru/book/59013 Неопубликованные материалы Л.Эйлера по теории чисел]. — "Наука", 1997.
- Проф. Д.Ф.Егоров. [lib.mipt.ru/book/59898 Элементы теории чисел]. — Государственное издательство Москва, 1923.
- Кордемский Б. А. [ilib.mccme.ru/djvu/klassik/smekalka.htm Математическая смекалка]. — М.: ГИФМЛ, 1958. — 576 с.
Ссылки
- [kvant.mccme.ru/1974/01/p77.htm Решето Эратосфена от М. Гарднера]
- [habrahabr.ru/post/91112/ Алгоритм составления таблицы простых чисел от заданного до другого числа]
- [www.mkyong.com/java/how-to-determine-a-prime-number-in-java/ Реализация алгоритма поиска простых чисел на Java]
- [e-maxx.ru/algo/eratosthenes_sieve Доказательство сложности алгоритма]
- [habrahabr.ru/post/133037/ Еще раз о поиске простых чисел]
Отрывок, характеризующий Решето Эратосфена
– Ты чего не видал, шалава… Граф спросит, а никого нет; иди платье собери.– Да я только за водой бежал, – сказал Мишка.
– А вы как думаете, Данило Терентьич, ведь это будто в Москве зарево? – сказал один из лакеев.
Данило Терентьич ничего не отвечал, и долго опять все молчали. Зарево расходилось и колыхалось дальше и дальше.
– Помилуй бог!.. ветер да сушь… – опять сказал голос.
– Глянь ко, как пошло. О господи! аж галки видно. Господи, помилуй нас грешных!
– Потушат небось.
– Кому тушить то? – послышался голос Данилы Терентьича, молчавшего до сих пор. Голос его был спокоен и медлителен. – Москва и есть, братцы, – сказал он, – она матушка белока… – Голос его оборвался, и он вдруг старчески всхлипнул. И как будто только этого ждали все, чтобы понять то значение, которое имело для них это видневшееся зарево. Послышались вздохи, слова молитвы и всхлипывание старого графского камердинера.
Камердинер, вернувшись, доложил графу, что горит Москва. Граф надел халат и вышел посмотреть. С ним вместе вышла и не раздевавшаяся еще Соня, и madame Schoss. Наташа и графиня одни оставались в комнате. (Пети не было больше с семейством; он пошел вперед с своим полком, шедшим к Троице.)
Графиня заплакала, услыхавши весть о пожаре Москвы. Наташа, бледная, с остановившимися глазами, сидевшая под образами на лавке (на том самом месте, на которое она села приехавши), не обратила никакого внимания на слова отца. Она прислушивалась к неумолкаемому стону адъютанта, слышному через три дома.
– Ах, какой ужас! – сказала, со двора возвративись, иззябшая и испуганная Соня. – Я думаю, вся Москва сгорит, ужасное зарево! Наташа, посмотри теперь, отсюда из окошка видно, – сказала она сестре, видимо, желая чем нибудь развлечь ее. Но Наташа посмотрела на нее, как бы не понимая того, что у ней спрашивали, и опять уставилась глазами в угол печи. Наташа находилась в этом состоянии столбняка с нынешнего утра, с того самого времени, как Соня, к удивлению и досаде графини, непонятно для чего, нашла нужным объявить Наташе о ране князя Андрея и о его присутствии с ними в поезде. Графиня рассердилась на Соню, как она редко сердилась. Соня плакала и просила прощенья и теперь, как бы стараясь загладить свою вину, не переставая ухаживала за сестрой.
– Посмотри, Наташа, как ужасно горит, – сказала Соня.
– Что горит? – спросила Наташа. – Ах, да, Москва.
И как бы для того, чтобы не обидеть Сони отказом и отделаться от нее, она подвинула голову к окну, поглядела так, что, очевидно, не могла ничего видеть, и опять села в свое прежнее положение.
– Да ты не видела?
– Нет, право, я видела, – умоляющим о спокойствии голосом сказала она.
И графине и Соне понятно было, что Москва, пожар Москвы, что бы то ни было, конечно, не могло иметь значения для Наташи.
Граф опять пошел за перегородку и лег. Графиня подошла к Наташе, дотронулась перевернутой рукой до ее головы, как это она делала, когда дочь ее бывала больна, потом дотронулась до ее лба губами, как бы для того, чтобы узнать, есть ли жар, и поцеловала ее.
– Ты озябла. Ты вся дрожишь. Ты бы ложилась, – сказала она.
– Ложиться? Да, хорошо, я лягу. Я сейчас лягу, – сказала Наташа.
С тех пор как Наташе в нынешнее утро сказали о том, что князь Андрей тяжело ранен и едет с ними, она только в первую минуту много спрашивала о том, куда? как? опасно ли он ранен? и можно ли ей видеть его? Но после того как ей сказали, что видеть его ей нельзя, что он ранен тяжело, но что жизнь его не в опасности, она, очевидно, не поверив тому, что ей говорили, но убедившись, что сколько бы она ни говорила, ей будут отвечать одно и то же, перестала спрашивать и говорить. Всю дорогу с большими глазами, которые так знала и которых выражения так боялась графиня, Наташа сидела неподвижно в углу кареты и так же сидела теперь на лавке, на которую села. Что то она задумывала, что то она решала или уже решила в своем уме теперь, – это знала графиня, но что это такое было, она не знала, и это то страшило и мучило ее.
– Наташа, разденься, голубушка, ложись на мою постель. (Только графине одной была постелена постель на кровати; m me Schoss и обе барышни должны были спать на полу на сене.)
– Нет, мама, я лягу тут, на полу, – сердито сказала Наташа, подошла к окну и отворила его. Стон адъютанта из открытого окна послышался явственнее. Она высунула голову в сырой воздух ночи, и графиня видела, как тонкие плечи ее тряслись от рыданий и бились о раму. Наташа знала, что стонал не князь Андрей. Она знала, что князь Андрей лежал в той же связи, где они были, в другой избе через сени; но этот страшный неумолкавший стон заставил зарыдать ее. Графиня переглянулась с Соней.
– Ложись, голубушка, ложись, мой дружок, – сказала графиня, слегка дотрогиваясь рукой до плеча Наташи. – Ну, ложись же.
– Ах, да… Я сейчас, сейчас лягу, – сказала Наташа, поспешно раздеваясь и обрывая завязки юбок. Скинув платье и надев кофту, она, подвернув ноги, села на приготовленную на полу постель и, перекинув через плечо наперед свою недлинную тонкую косу, стала переплетать ее. Тонкие длинные привычные пальцы быстро, ловко разбирали, плели, завязывали косу. Голова Наташи привычным жестом поворачивалась то в одну, то в другую сторону, но глаза, лихорадочно открытые, неподвижно смотрели прямо. Когда ночной костюм был окончен, Наташа тихо опустилась на простыню, постланную на сено с края от двери.
– Наташа, ты в середину ляг, – сказала Соня.
– Нет, я тут, – проговорила Наташа. – Да ложитесь же, – прибавила она с досадой. И она зарылась лицом в подушку.
Графиня, m me Schoss и Соня поспешно разделись и легли. Одна лампадка осталась в комнате. Но на дворе светлело от пожара Малых Мытищ за две версты, и гудели пьяные крики народа в кабаке, который разбили мамоновские казаки, на перекоске, на улице, и все слышался неумолкаемый стон адъютанта.
Долго прислушивалась Наташа к внутренним и внешним звукам, доносившимся до нее, и не шевелилась. Она слышала сначала молитву и вздохи матери, трещание под ней ее кровати, знакомый с свистом храп m me Schoss, тихое дыханье Сони. Потом графиня окликнула Наташу. Наташа не отвечала ей.
– Кажется, спит, мама, – тихо отвечала Соня. Графиня, помолчав немного, окликнула еще раз, но уже никто ей не откликнулся.
Скоро после этого Наташа услышала ровное дыхание матери. Наташа не шевелилась, несмотря на то, что ее маленькая босая нога, выбившись из под одеяла, зябла на голом полу.
Как бы празднуя победу над всеми, в щели закричал сверчок. Пропел петух далеко, откликнулись близкие. В кабаке затихли крики, только слышался тот же стой адъютанта. Наташа приподнялась.
– Соня? ты спишь? Мама? – прошептала она. Никто не ответил. Наташа медленно и осторожно встала, перекрестилась и ступила осторожно узкой и гибкой босой ступней на грязный холодный пол. Скрипнула половица. Она, быстро перебирая ногами, пробежала, как котенок, несколько шагов и взялась за холодную скобку двери.
Ей казалось, что то тяжелое, равномерно ударяя, стучит во все стены избы: это билось ее замиравшее от страха, от ужаса и любви разрывающееся сердце.
Она отворила дверь, перешагнула порог и ступила на сырую, холодную землю сеней. Обхвативший холод освежил ее. Она ощупала босой ногой спящего человека, перешагнула через него и отворила дверь в избу, где лежал князь Андрей. В избе этой было темно. В заднем углу у кровати, на которой лежало что то, на лавке стояла нагоревшая большим грибом сальная свечка.
Наташа с утра еще, когда ей сказали про рану и присутствие князя Андрея, решила, что она должна видеть его. Она не знала, для чего это должно было, но она знала, что свидание будет мучительно, и тем более она была убеждена, что оно было необходимо.
Весь день она жила только надеждой того, что ночью она уввдит его. Но теперь, когда наступила эта минута, на нее нашел ужас того, что она увидит. Как он был изуродован? Что оставалось от него? Такой ли он был, какой был этот неумолкавший стон адъютанта? Да, он был такой. Он был в ее воображении олицетворение этого ужасного стона. Когда она увидала неясную массу в углу и приняла его поднятые под одеялом колени за его плечи, она представила себе какое то ужасное тело и в ужасе остановилась. Но непреодолимая сила влекла ее вперед. Она осторожно ступила один шаг, другой и очутилась на середине небольшой загроможденной избы. В избе под образами лежал на лавках другой человек (это был Тимохин), и на полу лежали еще два какие то человека (это были доктор и камердинер).
Камердинер приподнялся и прошептал что то. Тимохин, страдая от боли в раненой ноге, не спал и во все глаза смотрел на странное явление девушки в бедой рубашке, кофте и вечном чепчике. Сонные и испуганные слова камердинера; «Чего вам, зачем?» – только заставили скорее Наташу подойти и тому, что лежало в углу. Как ни страшно, ни непохоже на человеческое было это тело, она должна была его видеть. Она миновала камердинера: нагоревший гриб свечки свалился, и она ясно увидала лежащего с выпростанными руками на одеяле князя Андрея, такого, каким она его всегда видела.
Он был таков же, как всегда; но воспаленный цвет его лица, блестящие глаза, устремленные восторженно на нее, а в особенности нежная детская шея, выступавшая из отложенного воротника рубашки, давали ему особый, невинный, ребяческий вид, которого, однако, она никогда не видала в князе Андрее. Она подошла к нему и быстрым, гибким, молодым движением стала на колени.
Он улыбнулся и протянул ей руку.
Для князя Андрея прошло семь дней с того времени, как он очнулся на перевязочном пункте Бородинского поля. Все это время он находился почти в постояниом беспамятстве. Горячечное состояние и воспаление кишок, которые были повреждены, по мнению доктора, ехавшего с раненым, должны были унести его. Но на седьмой день он с удовольствием съел ломоть хлеба с чаем, и доктор заметил, что общий жар уменьшился. Князь Андрей поутру пришел в сознание. Первую ночь после выезда из Москвы было довольно тепло, и князь Андрей был оставлен для ночлега в коляске; но в Мытищах раненый сам потребовал, чтобы его вынесли и чтобы ему дали чаю. Боль, причиненная ему переноской в избу, заставила князя Андрея громко стонать и потерять опять сознание. Когда его уложили на походной кровати, он долго лежал с закрытыми глазами без движения. Потом он открыл их и тихо прошептал: «Что же чаю?» Памятливость эта к мелким подробностям жизни поразила доктора. Он пощупал пульс и, к удивлению и неудовольствию своему, заметил, что пульс был лучше. К неудовольствию своему это заметил доктор потому, что он по опыту своему был убежден, что жить князь Андрей не может и что ежели он не умрет теперь, то он только с большими страданиями умрет несколько времени после. С князем Андреем везли присоединившегося к ним в Москве майора его полка Тимохина с красным носиком, раненного в ногу в том же Бородинском сражении. При них ехал доктор, камердинер князя, его кучер и два денщика.
Князю Андрею дали чаю. Он жадно пил, лихорадочными глазами глядя вперед себя на дверь, как бы стараясь что то понять и припомнить.
– Не хочу больше. Тимохин тут? – спросил он. Тимохин подполз к нему по лавке.
– Я здесь, ваше сиятельство.
– Как рана?
– Моя то с? Ничего. Вот вы то? – Князь Андрей опять задумался, как будто припоминая что то.
– Нельзя ли достать книгу? – сказал он.
– Какую книгу?
– Евангелие! У меня нет.
Доктор обещался достать и стал расспрашивать князя о том, что он чувствует. Князь Андрей неохотно, но разумно отвечал на все вопросы доктора и потом сказал, что ему надо бы подложить валик, а то неловко и очень больно. Доктор и камердинер подняли шинель, которою он был накрыт, и, морщась от тяжкого запаха гнилого мяса, распространявшегося от раны, стали рассматривать это страшное место. Доктор чем то очень остался недоволен, что то иначе переделал, перевернул раненого так, что тот опять застонал и от боли во время поворачивания опять потерял сознание и стал бредить. Он все говорил о том, чтобы ему достали поскорее эту книгу и подложили бы ее туда.
– И что это вам стоит! – говорил он. – У меня ее нет, – достаньте, пожалуйста, подложите на минуточку, – говорил он жалким голосом.
