网站正能量点进去就能看,免费建立自己喜欢的盒,深圳建设网站公司简介,四川手机网上营业厅最大公约数和最小公倍数
概念描述
最大公约数#xff08;GCD#xff09;是指两个或多个整数共有约数中的最大值。 最小公倍数#xff08;LCM#xff09;是指两个或多个整数共有的倍数中的最小值
方法介绍
碾转相除法
一种用于计算两个整数的最大公约数#xff08;GCD…最大公约数和最小公倍数
概念描述
最大公约数GCD是指两个或多个整数共有约数中的最大值。 最小公倍数LCM是指两个或多个整数共有的倍数中的最小值
方法介绍
碾转相除法
一种用于计算两个整数的最大公约数GCD的方法。它基于以下原理两个数的最大公约数等于其中较小数除以它们的余数的最大公约数。 该算法的步骤如下
将两个整数记为a和b其中a是较大的数b是较小的数。用a除以b得到一个商q和余数r。如果r等于0则b就是最大公约数算法结束。如果r不等于0则将a更新为bb更新为r然后返回第二步继续执行。重复执行步骤2-4直到余数为0为止。
两个数的乘积除以两个数的最大公约数即为两个数的最小公倍数
代码实现
求解最大公约数
public int gcd(int a, int b) {int k 0;while (k!0){k a%b;a b;b k;};return a;
}求解最小公倍数
public int mcl(int a, int b) {int gcd gcd(a, b);return a * b / gcd;
}素数与合数
概念介绍
素数又称为质数素数首先要满足大于等于2并且除了1和它本身之外不能被任何其他自然数整除。其他数都是合数。比较特殊的是1即非素素数也非合数。2是唯一的同时为偶数和素数的数字。
方法介绍
要判断一个数是否为质数可以使用以下方法
特殊情况处理首先排除小于2的数因为质数定义为大于1的自然数。试除法从2开始逐个将待判断的数除以从2到其平方根范围内的所有整数包括平方根如果能够整除则该数不是质数。如果在整个范围内都没有找到能整除的数则该数是质数。
代码实现
public boolean isPrime(int num){int max (int)Math.sqrt(num);for (int i 2; imax;i){if(num%i0){return false;}}return true;
}质数计数
问题描述
给定整数 n 返回所有小于非负整数 n 的质数的数量 。详见leetcode204
问题分析
最直接的方式就是从2开始遍历每次利用上面的质数判断代码对每一个数字进行判断如果是质数计数器➕1直至计数器为n返回当前质数。这样做时间复杂度过高。可以通过空间换时间的方式来操作设置一个长度为n的数组初始时设置数组全为1之后从下标2开始遍历如果数组当前值为1,质数计数器➕1并将当前数字的倍数以及与倍数相关的非质数下标设置为0最后返回质数计数器的值。这种方式也被称为埃氏筛
代码实现
直接方式
public int countPrimes(int n) {int count 0;for(int i2;in;i){if(isPrime(i)){count;}}return count;
}public boolean isPrime(int num){int max (int)Math.sqrt(num);for (int i 2; imax;i){if(num%i0){return false;}}return true;
}埃氏筛方式
public int countPrimes(int n) {int[] isPrime new int[n];int count 0;Arrays.fill(isPrime,1);for(int i2;in;i){if(isPrime[i]1){count;if((long)i*in){for(int ji*i;jn;ji){isPrime[j]0;}}}}return count;
}丑数判断
问题描述
丑数 就是只包含质因数 2、3 和 5 的正整数。
给你一个整数 n 请你判断 n 是否为 丑数 。如果是返回 true 否则返回 false 。详见leetcode263
问题分析
可以直接根据丑数的概念进行判断。如果不包含质因数或者包含质因数 2、3 和 5 的正整数即为丑数
代码实现
public boolean isUgly(int n) {if(n0){return false;}int[] factors new int[]{2,3,5};for(int factor:factors){while(n%factor0){n n/factor;}}return n1;
}丑数计数
问题描述
给你一个整数 n 请你找出并返回第 n 个 丑数 。详见leetcode264
问题分析
最直接的方式就是从1开始遍历每次利用上面的丑数判断代码对每一个数字进行判断如果是质数计数器➕1直至计数器为n返回当前丑数。这样做时间复杂度过高。可以通过空间换时间的方式来操作设置一个小顶堆初始时将最小的丑数1加入队中循环n次每次将堆顶元素x移除每次将2x,3x,5x放入堆中为了避免重复可以使用集合过滤循环n次之后最小的第n个丑数出堆返回
代码实现
直接方式
public int nthUglyNumber(int n) {int count 0;int i1;while(true){if(isUgly(i)){count;if(countn){return i;}}i;}
}public boolean isUgly(int num){if(num0){return false;}int[] factors new int[]{2,3,5};for(int factor:factors){while(num%factor0){num num/factor;}}return num1;
}最小堆方式
public int nthUglyNumber(int n) {int[] factors {2, 3, 5};SetLong seen new HashSetLong();PriorityQueueLong heap new PriorityQueueLong();seen.add(1L);heap.offer(1L);int ugly 0;for (int i 0; i n; i) {long curr heap.poll();ugly (int) curr;for (int factor : factors) {long next curr * factor;if (seen.add(next)) {heap.offer(next);}}}return ugly;
}
