質(zhì)數(shù)相關(guān)題目：
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逝薪，但是要注意查重的問題级遭，事實(shí)上時(shí)間復(fù)雜度還沒有for循環(huán)好。
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;
}
};
