1. 辗转相除法
辗转相除法又称欧几里得算法,求两个数的最大公因数,希腊数学家喜欢用图形来处理问题,于是将要求最大公约数问题转化为,以两个数字构成矩形,寻找可以铺满整个矩形的最大正方形的边长问题。
题目
例如8和12的最大公因数是4,记作gcd(8,12)=4,辗转相除法的规则是,若r是a%b的余数,则gcd(a,b)= gcd(b,r)。
计算gcd(546,429)
思路
希腊数学家是这样处理的,在我们预先构造的矩形中,我们先以矩形的短边构造正方形,然后再去计算这样的正方形可以在大矩形中「最多」放置多少个,这个计算过程可以用取余服务器托管网的方式进行计算。接下来,我们再用长边余下的长度构建正方形,在去试图铺满剩下未被覆盖的部分,然后计算这个正方形最多可以放置几个,直到我们找到这样一个正方形,这个正方形可以完全铺满整个大矩形。那么这个正方形就是我们最终要找的答案,自然而然的,这个正方形的边长也就是我们要找的两数的最大公约数。
代码
/**
* 辗转相除法
*/
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和自己整除的数是素数,其余的都是合数,
要求:给定一个正整数n(n
思路
从2开始对n进行取余测试,看是否出现n%i==0,如果出现就不是,理论上一直测试到n-1,但我们只需要测试到n^(1/2),至于为什么,大家可以思考一下,如果大于n^(1/2)中的一个数可以被n整数,其结构必定小于n^(1/2),这个数会被提前找到。
代码服务器托管网
/**
* 素数和合数
*/
public boolean isPrime(int num){
int max = (int) Math.sqrt(num);
for (int i = 2; i
拓展
Leetcode中的204题,用埃氏筛的方法来找素数,找到一个数,就把这个数的整数倍的数全部排除,排除完之后白色方块中剩余的就是素数,下面只是例子,并没有排除完,
选中2是素数,将2的倍数的数都排除(代码中将数组的位置标记为0)
选中3是素数,将3的倍数的数都排除
选中5是素数,将5的倍数的数都排除
代码2
/**
* 埃氏筛
*/
public int countPrimes(int n){
int[] isPrime = new int[n];
Arrays.fill(isPrime,1);
int ans = 0;
for (int i = 2; i
4. 丑数问题
题目
把质因子2、3和5的数称为丑数,按照从小到大的顺序输出第n个丑数
思路
若n是丑数,n可以写成n=2^a + 3^b + 5^c的形式,n反复除以2,3,5,若最后是1,则证明是丑数
代码
/**
* 丑数问题
*/
public boolean isUgly(int n){
if (n
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net