Вообще говоря, идею можно допилить до работоспособного состояния. Если посчитан набор простых чисел от 2 до sqrt(N) P[1..k], то количество простых чисел от 1 до N можно вычислить и так:
То есть надо взять все наборы из P[1..k], поделить нацело N на произведение чисел набора и результат отнять от N + k (если множителей в наборе нечетное количество) или прибавить (если четное). (Лишнее k взялось оттого, что N/P[i] - это количество всех чисел, делящихся на P[i], включая само P[i].)
Звучит на первый взгляд ужасно - наборов 2^k штук; но спасает возможность не рассматривать наборы с произведением, большим N. Это позволяет довольно хорошо обстричь рекурсию, и реальное количество делений будет не таким большим - для N = 10^6 я намерил 153192 деления, при том что честное решето дает 2197837 вычеркиваний. Правда, на Питоне решето все равно по скорости оказалось быстрее в полтора раза :-).
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
timeasmymeasure
no subject
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 вычеркиваний. Правда, на Питоне решето все равно по скорости оказалось быстрее в полтора раза :-).