Решение задачи про простые числа

[taki_net]

Задачу см. http://taki-net.livejournal.com/335594.html

Правильный ответ на первый вопрос дали почти все в разных вариациях: надо заранее посчитать любым способом (можно очень долго) простые числа до миллиона, вывести в файл, потом включить этот файл в программу в качестве начальных значений элементов массива (их около 72000), дальше организовать просмотр этого массива (хоть двоичным поиском, хоть линейно) и посчитать количество элементов этого массива, больших k и меньших n (он при этом даже не обязан быть сортированным). Вторая программа (с заранее созданным массивом) и была сдана. Кодится (не для любого компилятора) также такое решение: заранее посчитать массив от 1 до 1000000, в котором на i-м месте лежит кол-во простих чисел, меньших i. Программа состоит из одной строчки - вычитания из n-го эл-та массива k-го.

На второй вопрос - ответ под катом.

Жюри подразумевало, что участники должны реализовать решето Эратосфена "честно", не путем деления на все вообще числа меньшие корня (т.е. 1000) - это дает миллиард операций, а у нас в запасе только 200000000, и деление - дорогая операция, а путем правильно сделанного прореживания массива - удаления элементов, кратных простым числам, меньшим тысячи.

Другое возможное решение - тупым псевдоэратосфеном (деление на все до корня из верхней границы) найти все простые до 1000 - это 32000 делений и потом 1000 присваиваний, потом также тупо найти все простые до 1000000 - это около 145 млн. делений и миллион присваиваний потом. Но тут все уже зависит от "цены" деления. Может и не хватить времени.

Comments

[mbla.livejournal.com]

Я вчера не успела посмотреть задачку, но, вроде классичексий Эратосфен это и делает - прореживает, во всяком случае мы его так и обсуждаем, правда, не в школе, а на первом курсе :-))

[vdots.livejournal.com]

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

[mi-b.livejournal.com]

вот этим математики и отличаются от программистов

[buddha239.livejournal.com]

Там вроде как слишком все случайно.:) Шансов попасть маловато.:)

[kouzdra.livejournal.com]

путем деления на все вообще числа меньшие корня (т.е. 1000) - это дает миллиард операций, а у нас в запасе только 200000000

На самом деле намного меньше - во-первых - только на все простые (их чуть болше сотни). Во-вторых - деления прекращаются при первом найденном делителе - что сокращает потребное число делений еще наверное где-то на порядок.

[golergka.livejournal.com]

Так решение читерам засчитали или нет?

[taki-net.livejournal.com]

Об этом легенда умалчивает.

[http://users.livejournal.com/_iggi_/]

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

[kondybas.livejournal.com]

Хм. Мое решение не принято?

Среди чисел, меньших m, каждое второе делится на два, каждое третье - на три, каждое четвертое - на четыре и так далее.

Следовательно, количество непростых чисел, меньших m, равно:

SUM(m%2 + m%3 + m%4 + ... + m%int(sqrt(m)))

Неоптимальный метод требует двух вычислений частных сумм, оптимальный - одного. В любом случае, вичисление требует не более, чем 2*sqrt(10"6) - 2000 итераций.

[kondybas.livejournal.com]

Неоптимальный алгоритм

int count(int val)
{
   int retval = val;
   dlim = int(sqrt(val));

   for (d=2; d<dlim; d++)
      retval -= val % d;

   return retval;
}

int main()
{
   k = lolim;
   n = hilim;

   printf("%d\n", count(n) - count(k));
}

[vitus_wagner]

А как быть с числом 60? Оно ведь будет посчитано и среди делящихся на 2 и среди делящихся на 3, и на 4, и на 5, и на 6.

[kondybas.livejournal.com]

Ага. Дошло. Согласен.

[nickgrigoriev.livejournal.com]

Вообще говоря, идею можно допилить до работоспособного состояния. Если посчитан набор простых чисел от 2 до sqrt(N) P[1..k], то количество простых чисел от 1 до N можно вычислить и так:

N + k
- N/P[1] - N/P[2] - N/P[3] - N/P[4] - ...
+ N/(P[1]*P[2]) + N/(P[1]*P[3]) + N/(P[2]*P[3]) + ...
- N/(P[1]*P[2]*P[3]) - N/(P[1]*P[2]*P[4]) - ...

То есть надо взять все наборы из P[1..k], поделить нацело N на произведение чисел набора и результат отнять от N + k (если множителей в наборе нечетное количество) или прибавить (если четное). (Лишнее k взялось оттого, что N/P[i] - это количество всех чисел, делящихся на P[i], включая само P[i].)

Звучит на первый взгляд ужасно - наборов 2^k штук; но спасает возможность не рассматривать наборы с произведением, большим N. Это позволяет довольно хорошо обстричь рекурсию, и реальное количество делений будет не таким большим - для N = 10^6 я намерил 153192 деления, при том что честное решето дает 2197837 вычеркиваний. Правда, на Питоне решето все равно по скорости оказалось быстрее в полтора раза :-).

[vitus_wagner]

Вообще, честное решето Эратосфена в виде битовой шкалы из миллиона битов занимает 128Кбайт. А если хранить только нечетные числа (алгоритм прореживания от этого, что характерно, не меняется) то вообще 64К.
А если еще соптимизировать работу с малыми простыми числами (3,5,7) которые жрут больше всего времени, потому что требуют модификации каждого байта решета, то можно еще заметно сэкономить. Решето обрабатывать, естественно, не побайтно, а 32-разрядными словами.

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

Я в свое время с подобными вещами развлекался в dos realmode и 16-битном DPMI. Естествено на тех машинах оно работало не секунды. Но на 16Мб памяти (что заметно меньше, чем заявлено в условиях задачИ) выдавало простые числа не до миллиона, а до 128 миллионов. Учитывая, что сейчас процессоры быстрее как минимум на два порядка,
и решето меньше тоже на два порядка, в заявленные 2 секунды можно уложиться.

[bv.livejournal.com]

Ну вообще общая тенденция. То, где я раньше решал уравнения, берется численным методом в лоб.

демонстрируя совково-тоталитарное мышление (TM)

[erdferkel.livejournal.com]

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

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

[bljakhin-mukher.livejournal.com]

А, я тоже подумат что Эратосфен. Правда, без сугубых подробностей.

[vtail.livejournal.com]

А какого уровня это была олимпиада (класс, российская/городская) и какие вычислительные мощности компьютера, на котором всё проверяется? У меня на macbook написанное "в лоб" на Python решето Эратосфена (30 строк, 10 минут) занимает 1 секунду (и, соответственно, 4Мб памяти). Вроде бы если на С/С++ писать, будет заметно быстрее.

Это я к тому, что задача не кажется слишком сложной - это уровень школьников невысокий или уровень олимпиады?

[taki-net.livejournal.com]

Э, вопрос некорректный. Рассказали мне на всероссийской командной, но случилась она, конечно, не там. А может и вообще нигде.

[vtail.livejournal.com]

Простите, если он некорректный - у меня не было цели никого обидеть!

[taki-net.livejournal.com]

Я имел в виду "некорректный" в логическом смысле, а не моральном: в вопросе была презумпция того, что задача была дана на той же олимпиаде, на которой мне про нее рассказали:-)

[vtail.livejournal.com]

У меня была такая гипотеза, но прочтя новые строгие правила, я решил перестраховаться :)