### How to enumerate/count the numbers of a particular form below N in an efficient way?

Posted:

**Thu Sep 03, 2020 2:13 pm**For a sorted array of integers L={$a_1,a_2,...,a_k$}(Eg. L=[3,3,2,2,1]), consider numbers n which can be factored in the form:

$n=p_1^{a_1}p_2^{a_2}...p_k^{a_k}$, where $p_1, p_2,..., p_k$ are

Let E(L, N) be the enumerating function of all numbers n, not exceeding N, which has the prime factorization form given by L, and C(L, N) be the counting function of those numbers.

For example:

E({2,1}, 100)={12, 18, 20, 28, 44, 45, 50, 52, 63, 68, 75, 76, 92, 98, 99}

C({2,1}, 100)=15

E({2,2,1},1000)={180, 252, 300, 396, 450, 468, 588, 612, 684, 700, 828, 882, 980}

C([2,2,1], 1000)=13

For trivial or specific cases, such as L={1,1,1,1} or L={2,1}, it is easy to come up with an efficient algorithm(I have a recursive algorithm for L={1,1,1,1}). But for more general and complicated cases like E({5,5,3},$10^{18}$), it really beats me. Could anyone give me some hints to an efficient approach? The algorithm for E(L,N) and C(L,N) is useful in many PE problems. Thanks

$n=p_1^{a_1}p_2^{a_2}...p_k^{a_k}$, where $p_1, p_2,..., p_k$ are

**distinct primes**.Let E(L, N) be the enumerating function of all numbers n, not exceeding N, which has the prime factorization form given by L, and C(L, N) be the counting function of those numbers.

For example:

E({2,1}, 100)={12, 18, 20, 28, 44, 45, 50, 52, 63, 68, 75, 76, 92, 98, 99}

C({2,1}, 100)=15

E({2,2,1},1000)={180, 252, 300, 396, 450, 468, 588, 612, 684, 700, 828, 882, 980}

C([2,2,1], 1000)=13

For trivial or specific cases, such as L={1,1,1,1} or L={2,1}, it is easy to come up with an efficient algorithm(I have a recursive algorithm for L={1,1,1,1}). But for more general and complicated cases like E({5,5,3},$10^{18}$), it really beats me. Could anyone give me some hints to an efficient approach? The algorithm for E(L,N) and C(L,N) is useful in many PE problems. Thanks