1. 輾轉(zhuǎn)相除法

主要目的是獲取兩個數(shù)里面的最大公約數(shù)。

 public int gcd(int a, int b) {int k = 0;do {k = a % b;a = b;b = k;} while (k != 0);return a;}

2. 素數(shù)和合數(shù)

素數(shù)的要求是必須大于等于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 計數(shù)質(zhì)數(shù)

計數(shù)質(zhì)數(shù)
給定整數(shù) n ，返回 所有小于非負整數(shù) n 的質(zhì)數(shù)的數(shù)量 。
示例 1：
輸入：n = 10
輸出：4
解釋：小于 10 的質(zhì)數(shù)一共有 4 個, 它們是 2, 3, 5, 7 。
示例 2：

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

輸入：n = 1
輸出：0

2.2 枚舉法

質(zhì)數(shù)的定義：除了1和它本身，沒有其余的因數(shù)。而這道題目是用來同一某個元素內(nèi)出現(xiàn)質(zhì)數(shù)的個數(shù)，只需要再添加一個循環(huán)，用于判斷每個數(shù)是否是質(zhì)數(shù)，是就加一，而判斷方法就是上面的方法。

    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 是質(zhì)數(shù)，那么大于 xxx 的 xxx 的倍數(shù) 2x,3x,…2x,3x,\ldots2x,3x,… 一定不是質(zhì)數(shù)，因此我們可以從這里入手。
例如 2是素數(shù)，那么2的倍數(shù)一定不是素數(shù)，3也是同理，只需要使用一個標記是不是質(zhì)數(shù)，是質(zhì)數(shù)就標記為1，將不是質(zhì)數(shù)的標記為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. 丑數(shù)

定義：因數(shù)只包含2，3，5。當 n>0 時，若 n 是丑數(shù)，則 n 可以寫成 n = 2 ^ a + 3 ^ b + 5 ^ c 的形式，其中 a,b,c 都是非負整數(shù)。特別地，當 a,b,c 都是 000 時，n=1。

4.1 丑數(shù)

丑數(shù)
丑數(shù) 就是只包含質(zhì)因數(shù) 2、3 和 5 的正整數(shù)。
給你一個整數(shù) n ，請你判斷 n 是否為 丑數(shù) 。如果是，返回 true ；否則，返回 false 。

示例 1：

輸入：n = 6
輸出：true
解釋：6 = 2 × 3
示例 2：

輸入：n = 1
輸出：true
解釋：1 沒有質(zhì)因數(shù)，因此它的全部質(zhì)因數(shù)是 {2, 3, 5} 的空集。習慣上將其視作第一個丑數(shù)。
示例 3：

輸入：n = 14
輸出：false
解釋：14 不是丑數(shù)，因為它包含了另外一個質(zhì)因數(shù) 7 。

4.2 數(shù)學法

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