【LeetCode】数论题目总结

r囧r小猫 2022-10-17 04:23 287阅读 0赞

一、基本问题

1.  辗转相除的gcd应用，求最大公约数 ，进而lcm求最小公倍数
2.  质数问题
3.  余数问题、位运算、进制转换
4.  约数定理： 分解质因数.然后通过排列组合求因数个数,比如有n个质因数,每个质因数重复k1,k2…kn次,那么因数的个数=(k1+1)(k2+1)…(kn+1)

二、相关代码

1.  基本模板代码

/** * @param a * @param b * @return * 最大公约数 * 1.根据其值判断是否互质 * 2. */
        int gcd(int a,int b){ 
            if(a%b==0)
                return b;
            else
                return gcd(b,a%b);
        }
        // 最小公倍数
        int lcm(int a,int b){ 
            return a*b/gcd(a,b);
        }
        // 判断是否质数
        boolean isPrimer(int a){ 
            for(int i = 2;i*i<=a;i++){ 
                if(a%i==0)
                    return false;
            }
            return true;
        }
        // 判断是否互质
        boolean isRelativePrimer(int a,int b){ 
            return gcd(a, b) == 1?true:false;
        }
        // 判断集合是否两两互质
        //Set<Integer> set = new HashSet<>();
        boolean isSetPrimer(List<Integer> list){ 
            for(int i=0;i<list.size()-1;i++){ 
                for(int j=i+1;j<list.size();j++){ 
                    if(gcd(list.get(i),list.get(j))!=1){ 
                        return false;
                    }
                }
            }
            return true;
        }

1.  统计质数个数的优化

统计所有小于非负整数 n 的质数的数量。[204. 计数质数][204.]

直接枚举判断，超时；需要通过线性筛和埃氏筛进行降低时间复杂度。原理很简单，当发现i为质数时，那么肯定i的倍数就是非质数，采用一个hash表进行记录即可，若下次查hash表发现是非质数直接进行下一个。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjU0OTc0_size_16_color_FFFFFF_t_70_pic_center]

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] == 0) { 
                    ans += 1;
                    // 去除该质数倍数的数（2*i,3*i。。)降低时间复杂度
                    if ((long) i * i < n) { 
                        for (int j = i * i; j < n; j += i) { 
                            isPrime[j] = 1;
                        }
                    }
                }
            }
            return ans;
    
        }

[204.]: https://leetcode-cn.com/problems/count-primes/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjU0OTc0_size_16_color_FFFFFF_t_70_pic_center]: /images/20221014/2c1b80beaa824709aedd189ad17e1f0b.png