Primes

质数相关题目：
https://leetcode.com/problems/ugly-number/
https://leetcode.com/problems/ugly-number-ii/
https://leetcode.com/problems/super-ugly-number/
https://leetcode.com/problems/count-primes/

https://leetcode.com/problems/ugly-number/

class Solution {
public:
    bool isUgly(int num) {
        if (num == 1) return true;
        if (num <= 0) return false;
        while (num % 2 == 0) num /= 2;
        while (num % 3 == 0) num /= 3;
        while (num % 5 == 0) num /= 5;
        return num == 1;
    }
};

https://leetcode.com/problems/ugly-number-ii/
http://www.geeksforgeeks.org/ugly-numbers/

class Solution {
    int nthUglyNumber(int n) {
        vector <int> results (1,1);
        int i = 0, j = 0, k = 0;
        while (results.size() < n)
        {
            results.push_back(min(results[i] * 2, min(results[j] * 3, results[k] * 5)));
            if (results.back() == results[i] * 2) ++i;
            if (results.back() == results[j] * 3) ++j;
            if (results.back() == results[k] * 5) ++k;
        }
        return results.back();
    }
};   

https://leetcode.com/problems/super-ugly-number/
也可以用priority_queue，但是要注意查重的问题，事实上时间复杂度还没有for循环好。

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        vector<int> index(primes.size(), 0), ugly(n, INT_MAX);
        ugly[0]=1;
        for(int i=1; i<n; i++){
            for(int j=0; j<primes.size(); j++) ugly[i]=min(ugly[i],ugly[index[j]]*primes[j]);
            for(int j=0; j<primes.size(); j++) index[j]+=(ugly[i]==ugly[index[j]]*primes[j]);
        }
        return ugly[n-1];
    }
};    

count primes

class Solution {
public:
int countPrimes(int n) {
if(n<=2) return 0;
vector<bool> check(n, false);

        int result=1;
        int upper=sqrt(n);
        for(int i=3; i<n; i+=2){
            if(!check[i]){
                result++;
                if(i>upper) continue;
                for(int j=i*i; j<n; j+=i){
                    check[j]=true;
                }
            }
        }
        return result;
    }
};