Песни о Паскале

      Writeln(aFile);

end;

      {––––– Ввод множества границ (чисел) –––––}

procedure ReadSet(var aFile: text; var aSet : TBoundSet);

var k : integer;

begin

      While not Eoln(aFile) do begin

      Read(aFile, K); aSet:= aSet+[K];

      end;

      Readln (aFile);

end;

var FileIn, FileOut: text;

      R: TStateSet;       { множество соседей (результат) }

      SA, S : TBoundSet;       { границы царства «A» и прочих }

      State: char;       { буква с названием очередной страны }

begin       {––––– Главная программа –––––}

      Assign(FileIn, 'P_38_3.in'); Reset(FileIn);

      Assign(FileOut, ''); Rewrite(FileOut);

      R:= []; SA:=[]; State:='A'; { начнем с царства «A» }

      ReadSet(FileIn, SA); { из первой строки читаем границы для «A»}

      while not Eof (FileIn) do begin { цикл по странам }

      State:= Succ(State);       { буква следующей страны }

      S:=[]; ReadSet(FileIn, S); { читаем границы страны }

      { если граничит с царством «A», добавляем к результату }

      if S*SA <> [] then R:= R + [State];

      end;

      WriteCharSet(FileOut, R); Readln; { вывод результата }

      Close(FileIn); Close(FileOut);

end.

Программа Ника вычислила, что царство «A» соседствует с царствами «B», «D», «F», «I». Со временем проверка на местности это подтвердила.

Царь щедро наградил программиста, но история на этом не закончилась. О великом научном успехе скоро знала и последняя собака на материке. Но больше других этот успех заинтересовал купцов, плативших пошлины при пересечении границ. Они явились к Нику с предложением, от которого тот не смог отказаться. Хотите продолжения сказки? – оно ждёт вас в главах 49, 57 и 58.

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

Древние греки не знали, что они древние. И компьютеров тоже не знали, зато дышали бодрящим морским воздухом, коротая досуг в философских и математических размышлениях. Греческий досуг оказался не таким уж пустым, – иные задачки, придуманные под ласковый шепот волн, не решены по сию пору! Одна из них – вычисление простых чисел.

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

1 2 3 4 5 6 7 8 9 10

Здесь отмечены составные числа 4, 6, 8, 9 и 10, – они делятся без остатка либо на 2, либо на 3. Оставшиеся числа 1, 2, 3, 5 и 7 являются простыми.

Кто-то из греков задался вопросом: можно ли вычислить очередное простое число, если известны все предыдущие? Например, исходя из того, что числа 1, 2, 3 и 5 простые, определить следующее простое число (7). Как ни мудрили мудрецы, такой формулы или алгоритма пока не придумали! Но усилия в этом направлении породили целые отрасли математики, – вот такой полезный неуспех!

Размышлял над задачей и грек Эратосфен. Он тоже не решил её, однако нашел остроумный способ отсеивать простые числа, не превышающие некоторого числа N. Вот суть его идеи.

Положим, мы ищем простые числа не превышающие 20. Выпишем на морском песочке в ряд числа с 1 до 20. Первые два числа – 1 и 2 – простые, их не тронем, а среди остальных сотрем каждое второе, то есть 4, 6, 8 и так далее.

Затем находим первое нестертое число – это три. Сотрем каждое третье после тройки: 6, 9, 12, 15 и 18 (хотя часть из них уже стерта, лишний раз это сделать не повредит). Повторяя процедуру, находим следующее нестертое число – это пять. Стираем каждое пятое после пятерки: 10, 15, 20 (хотя все они уже стерты). Достигнув середины этого списка – числа 11, остановимся. Дальше двигаться нет смысла, поскольку на песке остались лишь простые числа.

Примечание. Если говорить точнее, лучше остановиться на числе, которое составляет корень квадратный из числа N, в данном случае это 5. Но для упрощения задачи мы будем обрабатывать больше чисел – половину ряда.

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

1-й отсев чисел, кратных 2:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

2-й отсев чисел, кратных 3: