алгебра - Нахождение простых чисел по версии капитана

Мне имело смысл "прогнать" программу при максимальных значениях, чтобы понять, какое число вариантов надо рассматривать при самом "грубом" способе перебора. Оно составляет где-то почти 6 миллионов, а это многовато. Тем не менее, если программа работает 3 секунды вместо требуемой одной, то алгоритм или его реализацию всегда можно слегка улучшить, не внося "радикальных" изменений.

Итак, я хочу начать с того, что при последовательных делениях на простые числа возникает определённое корневое дерево. Вверху находится число $%n$%. Из него идут вниз рёбра к вершинам $%[n/2]$%, $%[n/3]$%, $%[n/5]$%, ..., $%[n/p_m]$%. Число $%[n/2]$% мы далее делим с округлением на 3, 5, 7, 11, ..., и из него идут рёбра к соответствующим числам. И так на столько уровней вниз, пока числа после округлений остаются ненулевыми.

Строить полностью это дерево в процессе вычислений не требуется. Нам нужно всего лишь обходить каждую из его вершин в определённом порядке. Когда мы впервые посещаем очередную вершину, то к общей сумме мы прибавляем число $%\pm v$%, где $%v$% -- число, соответствующее данной вершине. Оно меняет знак с плюса на минус и обратно при спуске или поднятии на один уровень.

Запоминать в каждый текущий момент нам нужно только "ветку" дерева, ведущую из корня в просматриваемую вершину. Эта информация хранится в небольшом (менее 10 элементов) массиве. Вместе с числами (вершинами) в "параллельном" массиве мы запоминаем номер того простого числа, на который нам разрешено делить данное число $%v$%.

Покажем это на примере $%n=100$%, когда делить приходится на четыре простых числа: 2, 3, 5, 7. Хранимую информацию я буду записывать в виде пар (это как бы два массива). Начальная запись (100;1) означает, что рассматриваемся число 100, которое можно делить на самое первое простое число списка, то есть на два. Делаем это, и добавляем в массив пару (50;2). Теперь уже делить можно только на 3. Добавляем новую пару (16;3). Следующей будет (3;4). Здесь уже делить больше нельзя, поэтому возвращаемся назад. При этом нет необходимости менять массив, а достаточно иметь одну переменную (скажем, d), которая нам указывает номер просматриваемого элемента массива. Возврат назад означает выполнение команды d:=d-1, то есть мы переходим к паре (16;3), превращая её в (16;4), так как на третье простое число мы уже делили. Теперь после деления на 7 мы добавляем в массив пару (2;5), увеличивая d на 1, после чего идём назад (то есть d:=d-1). Это нас возвращает к (16;4), но 4 есть номер последнего простого числа. Снова делаем шаг назад (d:=d-1), и рассматриваем пару (50;2), превращая её в (50;3) и переходя от неё вниз к паре (10;4) после деления на 5. И так далее. Думаю, описываемый процесс ясен, равно как и то, какие слагаемые в его ходе добавляются к общей сумме.

Как я уже отмечал, для $%n$% порядка $%2\cdot10^9$% и для простых чисел в диапазоне 300, данное дерево имеет около $%6\cdot10^6$% вершин. Чтобы уменьшить это количество, увеличивая быстродействие программы в несколько раз, применим вот какое соображение.

Можно с самого начала отдельно учесть числа, делящиеся на 2 или на 3. Их количество на любом отрезке вычисляется по очень простой формуле. Всё, что туда не вошло, входит в одну из двух арифметических прогрессий: $%6k+1$% или $%6k+5$%. Каждую из прогрессий далее будем рассматривать по отдельности на предмет того, какие числа в ней делятся на 5, на 7, на 11, и так далее, и какие значения $%k$% этому соответствуют. Значения $%k$% при этом идут подряд, а диапазон для них сократится в 6 раз. Прогрессий две, то есть выигрыш во времени примерно втрое уже имеется. На самом деле, он будет существенно больше, так как при построении дерева делить надо будет только на простые числа, начиная с 5. Числа начинают убывать очень быстро, и число вершин дерева в размерах тоже уменьшается.

Последнее замечание касается подсчёта и суммирования. Допустим, нам надо понять, сколько членов прогрессии $%6k+5$% делится на, скажем, 17 при $%k$% от 2014 до 3000. Это несложная арифметическая задача: $%k$% должно при делении на 17 давать определённый остаток (в данном случае это 2), который в общем случае легко найти. И далее нужно подсчитать, сколько натуральных чисел удовлетворяет двойному неравенству $%2014\le17n+2\le3000$%, делается при помощи целочисленного деления.

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