Counting integers $n \leq x$ with a given prime signature

Given is a prime signature $S$ and an integer $x$. The task is to count how many integers $n$ exist such that $n \leq x$, and if $n = p_1^{k_1}p_2^{k_2}p_3^{k_3}p_4^{k_4}...$ then $S = (k_1,k_2,k_3,...)$. Let $C(S,x)$ be that count.

For example, if $S = (3,1,1)$ and $x=1000$ then there are $21$ such integers, being $$120, 168, 264, 280, 312, 408, 440, 456, 520, 552, 616, 680, 696, 728, 744, 760, 888, 920, 945, 952, 984$$

And so $C\big((3,1,1),1000\big )=21$. Notice that the order matters, so $270=2\cdot 3^3\cdot 5$ does not appear in this specific list. It would appear for $S=(1,3,1)$ for large enough $x$. The signature consists only of positive integers, and the primes are sorted in increasing order, $p_i

• Once the last part of $S$ is reached, call it $k_m$, count the number of primes smaller than $\sqrt[k_m]{\frac xn}$ and make sure only primes larger than $p_i$ are included. That is, add $\pi \Big(\sqrt[k_m]{\frac xn}\Big) - \pi(p_i)=\pi \Big(\sqrt[k_m]{\frac xn}\Big) - i$ to the total count.

It may be assumed the prime counting function implementation used for this algorithm is very efficient. Still, I have to compute $C(S,x)$ for thousands of signatures, and for $x=10^{12}$, so either my implementation of the above algorithm is lacking, or there is simply a better way to compute $C(S,x)$.

This is part of a recreational maths problem, but is in itself a nice problem, so any approaches to calculate the function efficiently are welcome.

Here is a complicated approach that might offer a modest improvement for values of $x$ of the size mentioned in your comment, when you want to compute $C(S,x)$ for many different $S$ and the same $x$:

Let me focus first on the case where $S$ has the form $S=(\cdots,1,1)$.

Let $f(u,v)$ be the number of integers of the form $p_1 p_2$ satisfying $u \le p_1u^2$. In particular, for each $v$, start by computing $f(1000,v)$, then $f(999,v)$, then $f(998,v)$, etc.

A more efficient approach is to store $f(u,v)$ only when $u \le 10^3$ is prime and $v \le 10^6$ is a product of two different primes. If we build a list of all products of two different primes $\le 10^6$, given any $u,v$, we can find the smallest prime $u'\ge u$ and the largest product of two primes $v' \ge v$ (via binary search in the list) and finally look up the value $f(u',v')$, using the fact that $f(u,v)=f(u',v')$. It will be possible to fill in the lookup table with a few million operations.

Once we've built the lookup table, it is now possible to offer an improved algorithm for computing $C(S,x)$ whenever $S$ has the form $S=(\cdots,1,1)$. In particular, use the same algorithm as in the question, but once the last two parts of $S$ are reached, if $n \ge x/10^6$ and $q\le 10^3$ where $q$ was the prime used in the third-to-last part, then compute $f(q,x/n)$, add $f(q,x/n)$ to the total count, and end the recursion. (If $nt$. In this way, for each $v$, we can fill in $g(t,v)$ in the order $g(997,v), g(991,v), g(983,v), g(977,v), \dots$. The lookup table will have fewer than $10^9$ entries and can be built with less than $10^9$ steps, so it is probably feasible to build it in a few seconds if implemented appropriately.

Once we've built the lookup table, we can use it to improve the algorithm for computing $C(S,x)$ whenever $S$ has the form $S=(\cdots,1,1,1)$. In particular, use the same algorithm as above, but once the last three parts of $S$ are reached, if $n \ge x/10^9$ and $q\le 10^3$ where $q$ was the prime used in the fourth-to-last recursion, then compute $g(q,x/n)$, add $f(q,x/n)$ to the total count, and end the recursion. (Otherwise, continue the algorithm as above).

Now you can reuse the $g$ lookup table for all $S$ that have the form $S=(\cdots,1,1,1)$.

You can optimize the parameters $10^3,10^9$ for performance, and do something similar for any other common suffix.

StackExchange Computer Science Q#154527, answer score: 2