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和它本身，沒有其余的因數。而這道題目是用來同一某個元素內出現(xiàn)質數的個數，只需要再添加一個循環(huán)，用于判斷每個數是否是質數，是就加一，而判斷方法就是上面的方法。

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