LeetCode 204. 计数质数 263. 丑数 264. 丑数 II

目录

204. 计数质数

263. 丑数

264. 丑数 II

---

204. 计数质数

统计所有小于非负整数 n 的质数的数量。
示例:
输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

---

此题最为核心的问题为：怎么判断一个数是否为质数？

什么是质数？

质数即为“除了1和自身外没有其他因数”的数，即：只能被1和自己整除的数

所以，判断一个数是否为质数，只要遍历比它小的所有数，能否整除它就好了！

    public boolean help(int n){
        for (int i = 2; i < n; i++) {
            if (n%i==0){
                return false;
            }
        }
        return true;
    }

---

真的有必要遍历所有小于它的数吗？

先给结论：没有！

事实上，只要遍历所有小于“根号n”的数就可以了！

为什么呢？

不妨用反证法证明：原命题为“若一个数n无法被小于等于根号n的所有数（当然不包括1）整除，则它一定是素数”

也就是说，一个数n无法被小于等于根号n的所有数（当然不包括1）整除，它一定无法被小于n大于根号n的数整除

逆否命题：存在一个数 它的因数大小只在根号n到n之间

ok，假设这个数n有一个大于根号n的因数x，那么，x能够整除n

也就是说，n/x得出一个整数y

y不可能为1，因为x小于n；y也不可能大于根号n，因为x大于根号n（若y也大于根号n，相乘必大于n，毕竟两个根号n相乘才等于n）。

也就是说，y是在1和根号n之间的！和命题“存在一个数 它的因数大小只在根号n到n之间”矛盾！

证伪成功！也就是原命题成立！

    public boolean help(int n){
        for (int i = 2; i < Math.sqrt(n); i++) {
            if (n%i==0){
                return false;
            }
        }
        return true;
    }

如此，判断一个数是否为质数的时间复杂度一下从O（n）变成O（n^1/2）

---

真的有必要遍历所有数吗？

仍然，没有！

只需要遍历所有小于根号n的素数即可

因为如果有一个小于根号n的非素数因数x，那么x的素因数一定也是n的因数

//ArrayList<Integer> arrayList为存已知质数的数组
    public boolean help(ArrayList<Integer> arrayList,int n){
        for (int i = 0; i < arrayList.size()&&arrayList.get(i)<=Math.sqrt(n); i++) {
            if (n%arrayList.get(i)==0){
                return false;
            }
        }
        return true;
    }

最后就成了：

class Solution {
    public int countPrimes(int n) {
        if (n<2){
            return 0;
        }
        ArrayList<Integer> arrayList=new ArrayList<>();
        arrayList.add(2);
        for (int i = 3; i < n; i++) {
            if(help(arrayList,i)){
                arrayList.add(i);
            }
        }
        return arrayList.size();
    }
    public boolean help(ArrayList<Integer> arrayList,int n){
        for (int i = 0; i < arrayList.size()&&arrayList.get(i)<=Math.sqrt(n); i++) {
            if (n%arrayList.get(i)==0){
                return false;
            }
        }
        return true;
    }
}

解法2

创建一个boolean数组存下标对应数是否为素数，初始化为true，从2开始遍历i，把下标为i倍数的置为false，当然只要遍历到根号n即可

class Solution {
    public int countPrimes(int n) {
        boolean[] isPrime = new boolean[n];
        Arrays.fill(isPrime,true);

        for(int i = 2; i * i < n; i++){
            if(isPrime[i]){
                for(int j = i * i; j < n; j = j + i){
                    isPrime[j] = false;
                }
            }
        }

        int count = 0;
        for(int i =2; i < n; i++){
            if(isPrime[i]) count++;
        }

        return count;
    }
}

时间短了不少呢

还有更短的，把偶数忽略即可

最短的那位，部分代码如下：

这？？？您可真是人才

263. 丑数

编写一个程序判断给定的数是否为丑数。
丑数就是只包含质因数 2, 3, 5 的正整数。

看起来很简单，用2，3，5除TMD！除到不能除了为止！

剩下个1就是丑数了，否则，它就不丑

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

264. 丑数 II

编写一个程序，找出第 n 个丑数。
丑数就是质因数只包含 2, 3, 5 的正整数。

简单！从小到大判断是不是丑数，计算是第几个丑数就完事了！

class Solution {
    public int nthUglyNumber(int n) {
        int count=0,flag=1;
        while(true){
            if(isUgly(flag)){
                count++;
                if(count==n){
                    return flag;
                }
            }
            flag++;
        }
    }
    public boolean isUgly(int num) {
        if(num<1){
            return false;
        }
        while(num%2==0){
            num/=2;
        }
        while(num%3==0){
            num/=3;
        }
        while(num%5==0){
            num/=5;
        }
        return num==1;
    }
}

然后。。。。。。

因为丑数分布是越来越稀疏的（10以内8个，100以内33个，1000以内85个），所以依次判断是否为丑数来找到第1000多个丑数，实在是太浪费时间了

那，用2^x *3^y *5^z 来把丑数全部找出来呢？

你这么知道找够了？（把小于某个数找齐，且个数大于n）

你怎么知道那个是第n个？（排序？）

看起来是很头疼的问题

按照大小顺序找就好了！

• 如果我们已经有一个从大到小的丑数序列，且它没有遗漏
• 下一个丑数一定是已有序列中，某个数*2/*3/*5

为什么？

不妨用反证法试试？

而且！对于下一个丑数，如果它是某个数i*2（2为例，3、5同理）所得，那么2i之前的所有数必定已经在这个集合中了

所以，我们用三个标记来标记，上一个*2/*3/5而加入数组的丑数对应的i，每次对比三个标记下一个数2/*3/*5的结果，取最小来加入我们的数组，如此慢慢增长，这个数组就是一个，递增的，没有遗漏的，丑数数组了

class Solution {
    public int nthUglyNumber(int n) {
        //235对应的标记
        int flag_2=0,flag_3=0,flag_5=0;
        //存丑数的数组
        ArrayList<Integer> arrayList=new ArrayList<>();
        arrayList.add(1);
        int count=1;
        while (count<n){
            if (arrayList.get(flag_2)*2<arrayList.get(flag_3)*3&&arrayList.get(flag_2)*2<arrayList.get(flag_5)*5){
                if(arrayList.get(flag_2)*2>arrayList.get(count-1)){
                    arrayList.add(arrayList.get(flag_2)*2);
                    count++;
                }
                flag_2++;
            }else if (arrayList.get(flag_3)*3<arrayList.get(flag_5)*5){
                if(arrayList.get(flag_3)*3>arrayList.get(count-1)){
                    arrayList.add(arrayList.get(flag_3)*3);
                    count++;
                }
                flag_3++;
            }else{
                if(arrayList.get(flag_5)*5>arrayList.get(count-1)){
                    arrayList.add(arrayList.get(flag_5)*5);
                    count++;
                }
                flag_5++;
            }
        }
        return arrayList.get(n-1);
    }
}

官方使用了一个先决条件：测试例中n<1690

假设我们以某种方式计算了第 n 个丑数，我们将这个解直接放到 Solution 类中的 nthUglyNumber 方法中。
让我们看一下上下文：有 596 个测试用例，其中大部分 n 是大于 50 小于 1691 的。
因此我们不必计算 596 \times 50 = 29800596×50=29800 的丑数，而是可以预计算 1690 个丑数，这样可以显著的加快提交速度。
如何预计算？使用另一个 Ugly 类在构造函数中完成所有丑数的预计算，然后声明一个 Ugly 类的实例对象，将该实例对象声明为 Solution 类的静态变量。
现在让我们来讨论两种不同的预计算方法。
作者：LeetCode
链接：https://leetcode-cn.com/problems/ugly-number-ii/solution/chou-shu-ii-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

简单来说就是，我们每个测试例中都从头开始生成，而官方题解中，只生成一次，用时自取即可