Я пользуюсь следующей модификациtq, позволяющий считать не только простые числа из некоторого интервала, но и произвольные функции

зависящие от разложения

Для этого предварительно выбирается шаг длины интервала

, у меня

. Вычисляются все простые числа меньше h (у меня их 2063689), вычисляются однобайтовые целые числа
![$lp[i]=[4\frac{\ln p[i]}{\ln 2}+0.5]$ $lp[i]=[4\frac{\ln p[i]}{\ln 2}+0.5]$](https://dxdy-01.korotkov.co.uk/f/4/5/4/454c9d9d8f001d51751b9da97b39cdc682.png)
(необходимо для распознования полной факторизации), вычисляются p- адические разложения
![$h=h_p(0)+h_p(1)p+...h_p(k)p^k, k=[\frac{2\ln h}{\ln p}]-1$ $h=h_p(0)+h_p(1)p+...h_p(k)p^k, k=[\frac{2\ln h}{\ln p}]-1$](https://dxdy-04.korotkov.co.uk/f/f/7/e/f7ee434b9479b6c42e83a6d03d881f3b82.png)
(этого достаточно для исследования в области чисел до

.
Тогда начальное число

раскладывается по каждому такому простому числу, вычисляется разложение

по каждому простому в той же памяти (вместо А). Тогда раскладываются на множители все числа вида

по циклу по простым р определяются шагом p, оно делится на

, если разложение

совпадает c разложением

в первых

цифрах (до k-1). В особенности удобно вычислять мультипликативные функции, зависящие несколько от самих простых, сколько от набора

и возможно от типа простого (например тип четное простое, нечетное простое вида 4k+1, нечетное простое вида 4k+3). Удобство здесь заключается в том, что в случае неполной факторизации по простым меньше h, не требуется вычисление оставшегося простого числа делением (тип можно определить и не вычисляя). Так все значения в интервале длины h вычисляются примерно за

операций, т.е. на разложение одного числа используется только

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