Здравствуйте, Кодт, Вы писали:

К>там будет что-то типа p * (какой-то ряд из int(count/p**k))

Это равно count * (p — 1), плюс совсем чуть-чуть, что за логарифмическое число шагов подбирается.

К>Кстати, если сплавить разложение и нахождение границы, то можно избавиться от вектора.

А смысл? Вектор простых делителей маленький, компилятор скорее всего соптимизирует его переприсвоения. Но сейчас нет смысла даже убирать логарифм, всё время (35ms) уходит на факторизацию, попробуйте вставить return factors.size(); в самое начала функции s после вычиления факторов. Сначала надо делать решето.

Здравствуйте, Кодт, Вы писали:

К>там будет что-то типа p * (какой-то ряд из int(count/p**k))

Это равно count * (p — 1), плюс совсем чуть-чуть, что за логарифмическое число шагов подбирается.

К>Кстати, если сплавить разложение и нахождение границы, то можно избавиться от вектора.

А смысл? Вектор простых делителей маленький, компилятор скорее всего соптимизирует его переприсвоения. Но сейчас нет смысла даже убирать логарифм, всё время (35ms) уходит на факторизацию, попробуйте вставить return factors.size(); в самое начала функции s после вычиления факторов. Сначала надо делать решето.


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