算法通过村第十三关-术数|黄金笔记|数论问题

---

前言

---

提示：难过的人伤心的人、在生活里面对困境的人、即将抑郁的人、从外面很难看出异样，人的心里却可能有一些裂痕。只是人不会再表面裂开。 --栾颖新《那个苹果也很好》

数论是一个很重要的学科，覆盖领域极广，小到小学的智力题目，大到世界顶级科学家都一直在研究的问题，也是因为其难度跨度非常大。在程序设计里面，也经常会出现数论问题的讨论，但是一般这些问题都比较基础，例如：素数问题、幂、对数、阶乘、幂运算、初等代数、几何问题、组合数学等等。这些问题中，组合数学等适合在回溯中讲解。几何问题过于繁琐，不利于做题。这里我们主要讨论素数和合数的问题来讲解，后续找到适合的题目在继续补充。

辗转相除法

辗转相除法又叫做欧几里得算法，是公元前300年左右的希腊数学家欧几里得在他的著作《几何原本》提出的。最大公约数（greatest common divisor 简称gcd），是指几个数的共有的因数之中最大的一个，例如8和12的最大公因数是4，记作gcd（8，12） = 4。辗转相除法的最重要的原则是，如果 r 是 a / b 的余数，则gcd(a,b) = gcd(b,r)。例如计算gcd(546,429):

gcd(546,429):

546 = 1(429) + 117
429 = 3(117) + 78
117 = 1(78) + 39  
78  = 2(39) 
因此：
gcd(546,429)
=gcd(429,117)
=gcd(117,78)
=gcd(78,39)  
=39    
1
2
3
4
5
6
7
8
9
10
11
12

该规则的证明可以，查一下相关资料，这里附上相关链接：[辗转相除法 - 维基百科，自由的百科全书 (wikipedia.org)]

我们这里看下如何利用循环，实现该代码：

    /**
     * 方法1： 循环实现辗转相除法
     *
     * @param a
     * @param b
     * @return
     */
    public static int gcd1(int a, int b) {// 循环实现
        // 保留余数
        int k = 0;
        do{
            // 拿到余数
            k = a % b;
            // 保留除数
            a = b;
            // 余数赋值给被除数
            b = k;
            // 注意循环条件
        }while(k != 0);
        // 最终返回除数
        return a;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

递归的方式也好解决：

    /**
     * 方法2：递归实现辗转相除法
     *
     * @param a
     * @param b
     * @return
     */
    public static int gcd2(int a, int b) {
        // 直到满足此条件逆归退出
        if (b == 0) {
            return a;
        }
        if (a < 0) {
            return gcd2(-a, b);
        }
        if (b < 0) {
            return gcd2(a, -b);
        }
        return gcd2(b, a % b);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

素数和合数

我们看下素数和合数的问题。素数又称为质数，素数首先要满足大于等于2，并且除了1和它本身之外，不能被任何其他自然数整除。其他数都是合数。比较特殊的是1既不是素数也不是合数。2是唯一的同时为偶数和素数的数字。

有了定义，自然第一个问题是怎么判断一个正整数是否为素数。题目要求：给定一个正整数 n （ n < 10 ^9)，判断它是否为素数。

基本上的方式是从2开始一次与n取余做测试，看是否出现 n % i == 0 的情况，如果出现了，则说明当前的 n 能被i整除，没有就不是。理论上这需要一直测试到 n - 1，都不是才说明它是素数。

而事实上也并不需要测试那么多，只要从 2 开始遍历一直到 n ^ (1/2) 就可以了，不用执行到 n - 1.这个使用明确的数学证明的，这里就不做赘述，如果不明白的话，可以查阅资料学习一下。所以代码实现也很简单：

    /**
     * 判断素数基本写法
     *
     * @param num
     * @return
     */
    public static boolean isPrime(int num) {
        // 这里取算术平方根  2 
        int max = (int) Math.sqrt(num);
        for (int i = 2; i <= max; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

基于该基础就可以造一些相关的题目了，推荐：

204. 计数质数 - 力扣（LeetCode）

用上述的方法嵌套一下就可以实现：

   public int countPrimes(int n) {
        int count = 0;
        for(int i = 2; i < n; i++){
            if(isPrime(i)){
                count++;
            }
        }
        return count;
    }
1
2
3
4
5
6
7
8
9

这个计算小的数据还行，但是计算比较大的数据就要考虑超时问题了，性能不好。我们接着往下看。

埃氏筛选法

为了高效的解决上述问题，有个筛选的方法：

埃拉托斯特尼筛法（希腊语：κόσκινον Ἐρατοσθένους，英语：sieve of Eratosthenes），简称埃氏筛，也称素数筛，是简单且历史悠久的筛法，用来找出一定范围内所有素数。

原理是从2开始，将每个素数的各倍数标记成合数。一个素数的各个倍数，是一个差为此素数本身的等差数列。此为这个筛法和试除法不同的关键之处，后者是以素数来测试能否整除每个待测数。

素数筛是列出所有小素数的有效方法，得名于古希腊数学家埃拉托斯特尼，并且描述在另一位古希腊数学家尼科马库斯所著的《算术入门》中。

作为现代筛法基础的勒让德筛法是埃拉托斯特尼筛法的简单推广。

详细列出算法如下：

1. 列出2以后所有数：
   • 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
2. 标记第一个质数2：
   • 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
3. 用红色标记2的倍数：
   • 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
4. 如果最大数不大于最后一个标出的素数的平方，那么剩下的所有的数都是质数，否则回到第二步。

看图：

    public int countPrimes(int n) {
        int[] primes = new int[n];
        int ans = 0;
        // 初始化数组
        Arrays.fill(primes,1);
        for(int i = 2; i < n; i++){
            if(primes[i] == 1){
                ans ++;
                // 筛选掉其他
                if((long) i * i < n){
                    for(int j = i*i; j < n; j+= i){
                        primes[j] = 0;
                    }
                }
            }
        }
        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

这个是经典的拿空间换时间的方法，想想一下这种场景在什么场合还可以用到。下面我们看看关于丑数的问题。

丑数问题

参考题目介绍：LCR 168. 丑数 - 力扣（LeetCode）

根据丑数的定义，0 和负整数一定不是丑数。

当 n > 0时，若 n 时丑数， 则 n 可以写成 n = 2 ^ a + 3 ^ b + 5 ^ c 的形式，其中 a， b， c 都是非负整数。特别是如果a、b、c 都为0 的时候， n == 1；

为了判断 n 是否满足上述形式，可以对n 反复除以 2、3、5.直到 n 不再包含质因数 2 ，3，5。如果剩下的数等于1，则说明 n 不包括其他质因数，是丑数； 否则说明 n 包含其他质因数，不是丑数。

所以代码可以这样写：

     /**
     * 第一种方法，直接计算比较
     *
     * @param index
     * @return
     */
    public static boolean isUgly(int index) {
        if (index < 0){
            return  false;
        }
        int[] factors = {2,3,5};
        for(int factor : factors){
            while(index % factor == 0){
                index /= factor;
            }
        }
        return index == 1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

思考一下，这里如果采用上面所说的埃氏筛选方法要怎么处理，发动一下脑筋。

---

总结

提示：辗转相除法；素数和合数；求解素数计算；丑数；筛法：

---

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ ("▔□▔)/

如有不理解的地方，欢迎你在评论区给我留言，我都会逐一回复 ~

也欢迎你 关注我 ，喜欢交朋友，喜欢一起探讨问题。