Оригинал: Об одном алгоритме поиска простых чисел

Как-то, ради интереса, я решил поискать в Сети материалы о нахождении всех простых чисел в диапазоне от 1 до N за линейное время. Нашлись некоторые статьи на английском, но описанные алгоритмы были несколько сложны для реализации. К сожалению, поиски на русском не увенчались успехом - были какие-то оптимизации, пытающиеся уменьшить объем памяти, константу в оценке времени, но ничего за O(N), так что я решил восполнить данный пробел.

Определение проблемы

Для начала, вспомним, что существует так называемое решето Эратосфена, позволяющее решать нашу задачу за O(N ln ln N):

bool notPrime[MAXN + 1];
int primes[MAXN];
 
int sieve(int n) {
	int primesCount = 0;
	int sqrt_n = (int)sqrt((double)n);
	for (int i = 2; i <= n; ++i) {
		if (!notPrime[i]) {
			primes[primesCount++] = i;
			if (i <= sqrt_n) {
				for (int j = i * i; j <= n; j += i) {
					notPrime[j] = true;
				}
			}
		}
	}
	return primesCount;
}

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

С разрешения автора выложена книга Основы программирования на языке Паскаль (Даулеткулов А.Б., Алматы, 2004).

Данное пособие является базовым курсом по основам программирования на языке Паскаль. Данный курс был опробирован в течении трех лет в Техническом лицее №28 г.Алматы. Пособие соответствует Государственному общеобразовательному стандарту среднего общего образования Республики Казахстан по предмету «Информатика». Особое внимание в нем уделено принципам структурного программирования.

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

Спасибо автору Даулеткулову А.Б. за предоставление pdf-версии книги.

С разрешения автора выложена книга Олимпиады по информатике (Даулеткулов А.Б., Алматы, 2004).

Книга состоит из трех частей.

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

Во второй части рассматриваются вопросы, связанные с технической, тактической и психологи-
ческой подготовкой учащихся к соревнованиям.

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

Спасибо автору Даулеткулову А.Б. за предоставление pdf-версии книги.

Предупреждение. Данная статья отражает исключительно мнение автора. Автор не претендует на верность всех утверждений. Статья предоставляется “как есть”, и автор не несет ответственности за какие бы то ни было отрицательные последствия ее прочтения и использования :)

Многие студенты, начав участвовать в олимпиадах, задаются вопросом: “Как добиться каких-либо значительных результатов?“. Здесь есть два варианта:

1. вы - гений, в этом случае, скорее всего, вам не надо читать дальше :)
2. вы - обычный студент, тогда единственный ответ - тренироваться, об этом и пойдет речь.

В последнее время меня несколько раз спрашивали “как надо готовиться к ACM ICPC“? В свое время и я задавал его некоторым личностям, но так и не получил вразумительного ответа. Поиск в Интернет также практически ничего не дал - видимо, известные корифеи спортивного программирования не очень любят писать. В общем пришлось, как всегда, доходить практически до всего самому, и здесь мне пригодился 7-летний опыт занятий некоторым, довольно специфическим видом спорта. Так или иначе, не без помощи руководителя и товарищей, я получил некоторый опыт, которым и постараюсь поделиться с вами - может кому-нибудь и пригодится.

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

Последняя статья об известных мне соревнованиях по программированию.

Долгое время ACM ICPC был единственным крупномасштабным официальным соревнованием. Однако несколько лет назад ситуация изменилась: ежегодно стал проводиться Открытый Кубок по программированию. Участвовать здесь могут все, но подавляющее большинство участников - представители СНГ. Спонсоры: Яндекс и CBOSS.

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

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

Пролог

Про TopCoder я случайно узнал в далеком 2005 году. Зашел на сайт, зарегистрировался, стал еженедельно получать email’ы с анонсом каких-то SRM’ов с призовым фондом $5000, но так и не решился поучаствовать - думал, нереально какому-то самоучке состязаться с профессионалами и еще претендовать на денежное вознаграждение. На участие сподвигнул меня Андрей Лопатин - двукратный чемпион мира по версии ACM ICPC, приехавший в Алматы в качестве тренера на школьные сборы в мае 2006. С тех пор я участвую почти в каждом Rated Event в секции Algorithm и ничуть не жалею об этом, даже если “сливаю” матч вчистую. Из материального заработал я немного - всего $523, которые при вычете налогов сильно уменьшаются в размере, несколько футболок и почти бесполезных вещиц. Но неоценим нематериальный вклад: возможность вживую пообщаться с легендарными личностями, посмотреть, как пишут программы профессионалы, шанс быть принятым на работу в известную компанию, ну и просто наслаждение и польза от самого процесса.

Итак, начнем-с…

В этой части попытаюсь начать разбираться с первой причиной малораспространенности олимпийского движения в Казахстане - неведеньем. Для начала рассмотрим IOI, Республиканскую студенческую олимпиаду и ACM ICPC.

Международная олимпиада по информатике (International Olympiad in Informatics, IOI) - самое известное соревнование среди школьников.

Про схему проведения можно почитать в Википедии

Пролог. Написал я как-то вечерком очередной SRM и подумал, а почему же так мало народу с Казахстана там участвует? Одна из причин - неведенье. С ней разберемся попозже. Ну а сейчас вторая…

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