Please help me with the following question.
There are three prime numbers given $p_1, p_2$ and $p_3$. Print the first $k$ numbers with only these prime numbers as factors.
Expected solution complexity: $O(k)$
For example: the three prime numbers are $2, 3, 7$.
First $7$ numbers with these as factors are $2, 3, 4, 6, 7, 8, 9$.
Best Answer
This is a graph problem where each node is a number of the form $n=p_1^{e_1}p_2^{e_2}p_3^{e_3}$ From every number there are three edge of the form $(n,p_in)$. You start exploring all the nodes from smallest to largest starting with $s=1$ (you ignore it later if you want) If you keep track of the visited nodes and the neighbors of them, the next node will be in the neighbor list, so you only need to pick the smallest and update the neighbors. Complexity of this approach is $O(k \cdot logk)$ since you need a heap and probably a set to maintain both sets (visited and neighbors).
I've got another algorithm that might improve the complexity of the previous. Let fix some value $T$ and generate all number of interest less than $T$. This can be done in the same way as I mention before. The complexity of this step is $O($Total numbers of interest less than $T)$. Now lets do the following: Start with $T=1$ and while the numbers you have found so far are less than $k$ let $T:=2\cdot T$. After we finish we will have at most $2\cdot k$ numbers. To recover the first $k$ elements you can find the $k^{th}$ element in linear time. So the total complexity of this algorithm will be $O(2 \cdot k + $Times we double $T)$ Since we know that $T \le 2\cdot p_1^{k}$ (Being $p_1$ the smallest among the three of them) $log(T)\le k\cdot log(p_1) + c$ So we will double $T$ at most $k \cdot log(p_1) $, I think a thigther bound might be proved but at least we have an algorithm which is $O(k + klog(p_1))$