数论问题
一、辗转相除法
辗转相除法又叫做欧几里得算法，是公元前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(inta,intb){
//循环实现
int k = 0;
do{
k = a%b;//得到余数
a = b;//根据辗转相除法，把被除数赋给除数
b = k;//余数赋给被除数
}while(k != 0);
return a;//返▣被除数
}
递归实现代码
public int gcd(int x, int y){
return x == 0 ? y : gcd(y % x, x);
}
二、素数与合数
判断素数与合数的函数
boolean isPrime(int num){
//判断num：从2判断到num^(1/2)即可
int max = (int)Math.sqrt(num);
for (int i = 2; i <= max; i++){
if (num % i == 0) return false; //合数
}
return true; //素数
}
LeetCode204 给定整数n，返回所有小于非负整数n的质数的数量
public int countPrimes(int n){
int sum = 0;
for (int i = 2; i < n; i++){
if（isPrime(i)){
sum++;
}
return sum;
}
boolean isPrime(int num){
//判断num：从2判断到num^(1/2)即可
int max = (int)Math.sqrt(num);
for (int i = 2; i <= max; i++){
if (num % i == 0) return false; //合数
}
return true; //素数
}
三、埃及筛
上面LeetCode204的题找素数的方法虽然能解决问题，但是效率太低，能否有效率更高一些的方法呢？
解决这个题有一个有效的方法，叫做埃氏筛，后来又产生了线性筛，奇数筛等改进的方法。
基本思想是如果是质数，那么大于×的y的倍数2X.3x…一定不是质数，因此我们可以从这一点入手。如下图所示：
先选中数字2,2是素数，然后将2的倍数全部排除（在数组里将该位置标记为0就行了）。
接着选中数字3,3是素数，然后将3的倍数全部排除。
接着选择数字5,5是素数，然后将5的倍数全部排除。
接着选择7,11,13一直到n，为什么4、6、8、9.不会再选择了呢？因为我们已经在前面的步骤中，将其变成0了。所以实现代码如下：
class Solution {
public int countPrimes(int n) {
int[] arr = new int[n];
int sum = 0;
for(int i = 2; i < n; i++){
if(arr[i] == 0){
sum++;
for(int j = 2; (long)j * i < n; j++) arr[j * i] = 1;
}
}
return sum;
}
}
当然这里还可以继续优化，对于一个质数 x，如果按上文说的我们从2x开始标记其实是冗余的，应该直接从x⋅x开始标记，因为 2x,3x,… 这些数一定在 xxx 之前就被其他数的倍数标记过了，例如2的所有倍数，3的所有倍数等。
class Solution {
public int countPrimes(int n) {
int[] arr = new int[n];
int sum = 0;
for(int i = 2; i < n; i++){
if(arr[i] == 0){
sum++;
if((long)i * i < n)
for(int j = i * i; j < n; j+= i) arr[j] = 1;
}
}
return sum;
}
}
四、丑数问题
Leetcode263 丑数就是只包含质因数2、3和5的正整数。给你一个整数n，请你判断n是否为丑数。如果是，返回true;否则，返回false
class Solution {
public boolean isUgly(int n) {
if(n <= 0) return false;
while(n % 2 == 0) n /= 2;
while(n % 3 == 0) n /= 3;
while(n % 5 == 0) n /= 5;
return n == 1;
}
}
