Kth Prime Number

Kth Prime Number

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

The eligible numbers are like 3, 5, 7, 9, 15 ...

Example

If k=4, return 9.

Challenge

O(n log n) or O(n) time

-------------------------- thinking --------------------------------
https://tianrunhe.wordpress.com/2012/04/03/find-the-kth-number-with-prime-factors-3-5-and-7/
-------------------------- codes --------------------------------
class Solution {
public:
    /*
     * @param k: The number k.
     * @return: The kth prime number as description.
     */
    long long kthPrimeNumber(int k) {
        // write your code here
        queue<long long> Q3;
        queue<long long> Q5;
        queue<long long> Q7;
        Q3.push(3);
        Q5.push(5);
        Q7.push(7);
        int out_cnt = 0;
        long long result;
        while (out_cnt < k) {
            out_cnt++;
            if (Q3.front() < Q5.front() && Q3.front() < Q7.front()) {
                result = Q3.front();
                Q3.pop();
                    Q3.push(result * 3);
                    Q5.push(result * 5);
                    Q7.push(result * 7);
            } else if (Q5.front() < Q3.front() && Q5.front() < Q7.front()) {
                result = Q5.front();
                Q5.pop();
                    Q5.push(result * 5);
                    Q7.push(result * 7);

            } else {
                result = Q7.front();
                Q7.pop();
                Q7.push(result * 7);
            }
        }
        return result;
    }
};