class Solution {
public:
    /*
     * @param n: An integer
     * @return: the nth prime number as description.
     */
    int nthUglyNumber(int n) {
        // write your code here
        if (n == 1) {
            return 1;
        }
        struct compare {
            bool operator() (long l, long r) {
                return l > r;
            }
        };
        set<long> unique;
        vector<long> prime;
        prime.push_back(2);
        prime.push_back(3);
        prime.push_back(5);

        unique.insert(2);
        unique.insert(3);
        unique.insert(5);


        int count = 1;
        priority_queue<long, vector<long>, compare> pQ;
        pQ.push(2);
        pQ.push(3);
        pQ.push(5);
        while (!pQ.empty()) {
            long top = pQ.top();
            pQ.pop();
            count++;
            if (count == n) {
                return top;
            }

            for (int i = 0; i < 3; i++) {
                if (unique.find(top * prime[i]) == unique.end()) {
                    pQ.push(top * prime[i]);
                    unique.insert(top * prime[i]);
                }
            } 
            cout<<"pQ.top"<<pQ.top()<<endl;


        }

    }
};