【蓝桥杯Java组】数论基础—素数筛、最大公约数、最小公倍数
🍈前言:
- 一学就会的小技巧(一):前缀和
- 一学就会的小技巧(二):差分
- 一学就会的小技巧(三):快速幂
- 一学就会的小技巧(四):龟速乘
- 一学就会的小技巧(五):矩阵快速幂
- 一学就会的小技巧(六):矩阵快速幂的应用
- 省赛真题—K倍区间(前缀和,数学,思维)
☕☕在解决编程题时,除了要对算法本身有足够的了解,往往还需要掌握一些基础数论。
☕☕常用的数论有:
- 最大公约数
- 最小公倍数
- 判断两数互质
- 素数筛
👩🏻🏫下面逐一给出代码模板~
👉🏻1.最大公约数:
🍺求解最大公约数使用辗转相除法,又叫做欧几里得算法。
🍺先将大数除以小数,如果整除,小数就是它们的最大公因数,如果不能整除,就记下余数,用前面的除数(就是小数),除以这个余数,以下类推,每一次都用前一个除式的除数除以自己的余数,直到有一个除法能整除,这时,最后能整除的除式的除数,就是这两个数的最大公因数。
🍦Java代码:
public static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
👉🏻2.最小公倍数:
🍺求两个数的最小公倍数可以先将两数相乘,再除以它们的最大公约数。
🍦Java代码:
public static int lcm(int a, int b) {
return (a * b) / gcd(a, b);
}
👉🏻3.判断两数互质
🍺知道如何求解最大公约数的话,很容易想到如何判断两数互质~
🍦Java代码:
public static boolean isRelativelyPrime(int a, int b) {
return gcd(a, b) == 1;
}
👉🏻4.素数筛
⛅素数又叫质数,素数筛用来统计素数的个数,分为线性筛、埃氏筛、欧拉筛、奇数筛…一般常用埃氏筛。
⭐以LeetCode204.计数质数为例~
⭐埃氏筛原理:
判断自然数n以内的全部质数,将不大于 n \sqrt{n} n的所有质数的倍数剔除,剩下的即为该自然数n以内的所有质数
-
Step 1. 先将整个序列均标记为质数
-
Step 2. 取出整个序列的第一个质数 P,此时为 2
-
Step 3. 将该质数在n以内的倍数全部标记为非质数
-
Step 4. 根据标记信息按序取该序列中下一个质数Q(此时为3),先判断其平方值是否超过n,如果是,则该算法结束,质数与否标记完成;否则,返回Step 3
🍦Java代码:
class Solution {
public int countPrimes(int n) {
boolean[] isPrimeArray = new boolean[n];
Arrays.fill(isPrimeArray, true);
for (int i = 2; i * i < n; i++) {
if (isPrimeArray[i]) {
int x = i;
// 从i*i开始标记,因为i*i之前的肯定标记过了,减少冗余
while (i * x < n) {
isPrimeArray[i * x] = false;
x++;
}
}
}
int count = 0;
for (int i = 2; i < n; i++)
if (isPrimeArray[i])
count++;
return count;
}
}
🍌🍌🍌
本文介绍了几个基础数论的知识,素数筛、互质判断、最大公约、最小公倍,它们很常用,一定要记住代码模板~
🍍🍍🍍
创作不易,如果觉得本文对你有所帮助的话请动动小手,给博主点个免费的赞吧。🙇🏻♀️
🍉🍉🍉
@作者:Mymel_晗,计科专业大学牲菜狗一枚,请大佬们多多关照~
相关文章
- Jmeter里的全能java测试sampler - Java request
- Java面向对象基础--对象数组
- Java语法基础(三)----选择结构的if语句、switch语句
- JAVA学习(一):Java介绍及其平台、开发环境的配置与搭建
- Java实现 蓝桥杯VIP 基础练习 完美的代价
- Java实现 蓝桥杯VIP 基础练习 分解质因数
- Java实现 蓝桥杯VIP 基础练习 字符串对比
- Java实现 蓝桥杯VIP 基础练习 时间转换
- Java实现 蓝桥杯 蓝桥杯VIP 基础练习 数的读法
- Java实现 蓝桥杯VIP 基础练习 FJ的字符串
- Java实现 蓝桥杯VIP 基础练习 龟兔赛跑预测
- Java实现 蓝桥杯VIP 基础练习 报时助手
- Java实现 蓝桥杯VIP 基础练习 Huffuman树
- Java实现 蓝桥杯VIP 基础练习 高精度加法
- java.lang.OutOfMemoryError: Java heap space 解决方法
- 【一起学Java-第三篇】Java语言基础
- 【java基础】接口(interface)
- 【java】Java线程池实现原理及业务中的实践