算法通关村——数论问题

2023-12-13 23:50:05

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

关卡名

数论问题

我会了??

内容

1.理解素数和合数如何判断

??

2.理解埃式筛的原理和工作过程

??

?1 辗转相除法

辗转相除法又叫做欧几里得算法,是公元前 300 年左右的希腊数学家欧几里得在他的著作《几何原本》提出的。最大公约数(greatest common divisor,简写为gcd),是指几个数的共有的因数之中最大的一个,例如 8 和 12 的最大公因数是 4,记作 gcd(8,12)=4。辗转相除法最重要的规则是,若 r 是 a ÷ b 的余数, 则gcd(a,b) = gcd(b,r)。例如计算 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

该规则的证明我们不做过多解释,感兴趣的同学可以看一下如何证明辗转相除法(欧几里德算法)? - 知乎。我们只看基于该结论如何实现,循环实现代码如下:

int gcd(int a, int b) {// 循环实现
    int k = 0;
    do {
      k = a % b;// 得到余数
      a = b;// 根据辗转相除法,把被除数赋给除数
      b = k;// 余数赋给被除数
    } while (k != 0);
    return a;// 返回被除数
  }

2 素数和合数?

我们看一下素数和合数的问题。素数又称为质数,素数首先要满足大于等于2,并且除了1和它本身之外,不能被任何其他自然数整除。其他数都是合数。比较特殊的是1即非素数,也非合数。2是唯一的同时为偶数和素数的数字。
有了定义,自然第一个问题就是如何判断一个正整数是否为素数。题目要求:给定一个正整数n(n<10^9),判断它是否为素数。
基本的方式是从2开始依次与n取余测试,看看是否出现n%i==0的情况,如果出现了则说明当前的n能被i整除,所以就不是。理论上一直测试到n-1,假如都不是,那就是素数了。
而事实上不需要测试这么多,只要从2开始遍历一直到n^(1/2)就可以 ,不用执行到n-1。这个是有明确的数学证明的,我们不再赘述,如果不知道请回家问高中老师。所以实现代码就是:

boolean isPrime(int num) {
  int max = (int)Math.sqrt(num);
  for (int i = 2; i <= max; i++) {
        if (num % i == 0) {
             return false;
         }
      }
   return true;
    }

基于该基础,就可以造题了,例如LeetCode204 给定整数 n ,返回 所有小于非负整数 n 的质数的数量 。

示例1:

输入:n = 10

输出:4

解释:小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

这个问题几乎就是将上面的代码再套一层就行了,直接遍历:

public int countPrimes(int n) {
        int cnt = 0;
        for (int i = 2; i < n; i++) {
            if (isPrime(i)) {
                cnt++;
            }
        }
        return cnt;
}

这个方法计算小的数据没有错,但是计算比较大的n仍然会超时,还是性能不够。我们下一节继续研究。

3 埃氏筛?

上面LeetCode204 的题找素数的方法虽然能解决问题,但是效率太低,能否有效率更高一些的方法呢?
解决这个题有一个有效的方法,叫做埃氏筛,后来又产生了线性筛, 奇数筛等改进的方法。
基本思想是如果 x是质数,那么大于 x 的 xy的倍数 2x. 3x… 一定不是质数,因此我们可以从这一点入手。如下图所示:

我们先选中数字2,2是素数,然后将2的倍数全部排除(在数组里将该位置标记为0就行了)。
接着我们选中数字3,3是素数,然后将3的倍数全部排除。
接着我们选择数字5,5是素数,然后将5的倍数全部排除。
接着我们选择 7,11,13一直到n,为什么 4 、6、8 、9 ...不会再选择了呢?因为我们已经在前面的步骤中,将其变成0了。所以实现代码如下:

public int countPrimes(int n) {
    int[] isPrime = new int[n];
    Arrays.fill(isPrime,1);
    int ans = 0;
    for(int i=2;i<n;i++){
        if(isPrime[i]==1){
            ans++;
            if((long)i * i<n){
                for(int j=i*i;i<n;j+=i){
                    isPrime[j] = 0;
                }
            }
        }
    }
    return ans;
}

这个是典型的以空间换时间的算法,这种思想在解决一些问题的时候可以参考,例如下面的丑数这个题。

4.丑数问题?

这个是剑指offer中的题目,我们把只包含质因子 2、3 和 5 的数称作丑数(Ugly Number),求按从小到大的顺序的第 n 个丑数。

示例:

输入: n = 10

输出: 12

解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

根据丑数的定义,0 和负整数一定不是丑数。
当 n>0 时,若 n 是丑数,则 n 可以写成 n = 2^a + 3^b + 5^c 的形式,其中 a,b,c 都是非负整数。特别地,当 a,b,c 都是 000 时,n=1。
为判断 n 是否满足上述形式,可以对 n 反复除以 2,3,5,直到 n 不再包含质因数 2,3,5。若剩下的数等于 1,则说明 n 不包含其他质因数,是丑数;否则,说明n包含其他质因数,不是丑数。
因此可以得到如下解答方式:

    public boolean isUgly(int n) {
        if (n <= 0) {
            return false;
        }
        int[] factors = {2, 3, 5};
        for (int factor : factors) {
            while (n % factor == 0) {
                n /= factor;
            }
        }
        return n == 1;
    }

本题也可以使用上面介绍的埃氏筛方式来解决 ,你可以思考一下如何做。?

文章来源:https://blog.csdn.net/m0_53401014/article/details/134798853
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。