算法通关村——数论经典问题解析

1. 辗转相除法

主要目的是获取两个数里面的最大公约数。

 public 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和它本身整除。

判断的方法比较简单，就是从2开始到n一直相除，判断是否等于0。但是其实可以不需要判断到n，到根号n即可。

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

2.1 计数质数

计数质数
给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。
示例 1：
输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
示例 2：

输入：n = 0
输出：0
示例 3：

输入：n = 1
输出：0

2.2 枚举法

质数的定义：除了1和它本身，没有其余的因数。而这道题目是用来同一某个元素内出现质数的个数，只需要再添加一个循环，用于判断每个数是否是质数，是就加一，而判断方法就是上面的方法。

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

不过这样写是力扣测试通过不了，效率太低。

3. 埃氏筛

定义：如果 xxx 是质数，那么大于 xxx 的 xxx 的倍数 2x,3x,…2x,3x,\ldots2x,3x,… 一定不是质数，因此我们可以从这里入手。
例如 2是素数，那么2的倍数一定不是素数，3也是同理，只需要使用一个标记是不是质数，是质数就标记为1，将不是质数的标记为0。

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

4. 丑数

定义：因数只包含2，3，5。当 n>0 时，若 n 是丑数，则 n 可以写成 n = 2 ^ a + 3 ^ b + 5 ^ c 的形式，其中 a,b,c 都是非负整数。特别地，当 a,b,c 都是 000 时，n=1。

4.1 丑数

丑数
丑数 就是只包含质因数 2、3 和 5 的正整数。
给你一个整数 n ，请你判断 n 是否为 丑数 。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：n = 6
输出：true
解释：6 = 2 × 3
示例 2：

输入：n = 1
输出：true
解释：1 没有质因数，因此它的全部质因数是 {2, 3, 5} 的空集。习惯上将其视作第一个丑数。
示例 3：

输入：n = 14
输出：false
解释：14 不是丑数，因为它包含了另外一个质因数 7 。

4.2 数学法

 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;}