Find the kth number with only prime factors of 3, 5 and 7

Design an algorithm to find the kth number such that the only prime factors are 3, 5, and 7.

It is a difficult question. But lets try to examplify it first.

we will have 3, 5, 7, 9, 15, 21, 25, 27, 35 , 45 … The way we do it is we first get 3, 5 and 7, then we multiply 3 with 3, 5, 7 and then 5 with 3, 5, 7 and 7 with 3,5,7, we do not know the order of the result, but what we do know is that 3^(i+1)*5^j*7^k > 3^i*5^j*7^k, same for 7 and 9, so we can have 3 queues Q3, Q5 and Q7, to store the elements of factor 3, 5 and 7, and a result to count the number of elements.

Process goes as follows
1. add 3, 5 and 7 to the corresponding queue.
2. remove the smallest element out of the head of the three Queue and count++.
3. if element x was removed from Q3, add 3*x, 5*x and 7*x to Q3, Q5 and Q7
if element x was removed from Q5, add 5*x and 7*x to Q5 and Q7
if element x was removed from Q7, add 7*x to Q7
(This step will make sure that when you removed a number that is 3^i*5^j*7^k, the i+1, j+1 and k+1 number will be pushed into the corresponding queue)
4. if has not count to k, go back to 2.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s