263. Ugly Number
注意：1.小于等于0都不属于丑数
2.while循环的判断不是num >= 0, 而是能被2 、3、5整除，即能被整除才去除这些数
class Solution {
public:
bool isUgly(int num) {
if(num <= )
return false;
while(num % == )
num /= ;
while(num % == )
num /= ;
while(num % == )
num /= ;
return num == ? true : false;
}
};
264. Ugly Number II
用一个数组去存第n个前面的所有整数，然后记录2 、3、5当前数的索引，每次选择最小的数。注意每次满足最小数，是索引加1，不是数值本身加1
class Solution {
public:
int nthUglyNumber(int n) {
int result[n + ];
result[] = ;
int index = ,index2 = ,index3 = ,index5 = ;
while(index < n){
index++;
int num2 = result[index2] * ;
int num3 = result[index3] * ;
int num5 = result[index5] * ;
int min_num = min(num2,min(num3,num5));
result[index] = min_num;
if(num2 == min_num)
index2++;
if(num3 == min_num)
index3++;
if(num5 == min_num)
index5++;
}
return result[n];
}
};
313. Super Ugly Number
这个和Ugly Number II 几乎是一样的，不同的是Ugly Number II是固定了2 、3、5这三个数，这个题是给一个数组。
class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
int result[n+];
result[] = ;
vector<int> index(primes.size(),);
int ind = ;
while(ind < n){
ind++;
int min_num = INT_MAX;
for(int i = ;i < primes.size();i++)
min_num = min(result[index[i]] * primes[i],min_num);
result[ind] = min_num;
for(int i = ;i < primes.size();i++){
if(result[index[i]] * primes[i] == min_num)
index[i]++;
}
}
return result[n];
}
};
204. Count Primes
质数（prime number）又称素数，有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。
这个题跟丑数的题一样，也需要用数组存。
思路：用j=2一个一个乘以质数i，只要乘到的值都不是质数，因为质数只能是1和他本身
class Solution {
public:
int countPrimes(int n) {
if(n <= )
return ;
vector<bool> flag(n+,true);
int count = ;
for(int i = ;i < n;i++){
if(flag[i] == true){
count++;
for(int j = ;j*i < n;j++)
flag[j*i] = false;
}
}
return count;
}
};
https://www.jianshu.com/p/12c0e91c696e
https://blog.csdn.net/github_39261590/article/details/73864039 图解
更新代码：
如果问题变成：求不超过10000的最大质数？用最快方法找到1到10000的质数？
只要把上面代码里面为false的坐标+1就可以得到，但是有个问题，子循环是j=1开始的，也就是会把当前的质数也变成true，对于计算个数问题不大，但是你如果要再把这些提取出来就错误了，从2开始才是真正可以泛化到其他两个问题的通用代码