263. Ugly Number
注意：1.小于等于0都不属于丑数
2.while循环的判断不是num >= 0, 而是能被2 、3、5整除，即能被整除才去除这些数
class Solution { public: bool isUgly(int num) { 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 ? true : false; } };
264. Ugly Number II
用一个数组去存第n个前面的所有整数，然后记录2 、3、5当前数的索引，每次选择最小的数。注意每次满足最小数，是索引加1，不是数值本身加1
class Solution { public: int nthUglyNumber(int n) { int result[n + 1]; result[1] = 1; int index = 1,index2 = 1,index3 = 1,index5 = 1; while(index < n){ index++; int num2 = result[index2] * 2; int num3 = result[index3] * 3; int num5 = result[index5] * 5; 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+1]; result[1] = 1; vector<int> index(primes.size(),1); int ind = 1; while(ind < n){ ind++; int min_num = INT_MAX; for(int i = 0;i < primes.size();i++) min_num = min(result[index[i]] * primes[i],min_num); result[ind] = min_num; for(int i = 0;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 <= 1) return 0; vector<bool> flag(n+1,true); int count = 0; for(int i = 2;i < n;i++){ if(flag[i] == true){ count++; for(int j = 2;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开始才是真正可以泛化到其他两个问题的通用代码