珠宝玉器监测网站建设方案,安徽做网站,怎样制作微信网站,网站域名登记证明文件数论是一个很重要的学科#xff0c;覆盖领域极广#xff0c;小到小学的智力问题#xff0c;大到世界顶级科学家都一直在研究相关问题#xff0c;因此其难度跨度非常大。在程序设计里 #xff0c;也经常会出现数论的问题#xff0c;但是#xff0c;这些一般都是比较基本的… 数论是一个很重要的学科覆盖领域极广小到小学的智力问题大到世界顶级科学家都一直在研究相关问题因此其难度跨度非常大。在程序设计里 也经常会出现数论的问题但是这些一般都是比较基本的数论问题例如素数问题、幂、对数、阶乘、幂运算、初等数论、几何问题、组合数学等等。这些问题中组合数学等适合在回溯里讲解。几何问题则过于繁琐 不利于做题。本部分我们暂时只以宿舍和合数的问题来讲解后续找到合适的题目继续来补充。 关卡名 数论问题 我会了✔️ 内容 1.理解素数和合数如何判断 ✔️ 2.理解埃式筛的原理和工作过程 ✔️ 1 辗转相除法
辗转相除法又叫做欧几里得算法,是公元前 300 年左右的希腊数学家欧几里得在他的著作《几何原本》提出的。最大公约数greatest common divisor简写为gcd是指几个数的共有的因数之中最大的一个例如 8 和 12 的最大公因数是 4记作 gcd(8,12)4。辗转相除法最重要的规则是若 r 是 a ÷ b 的余数, 则gcd(a,b) gcd(b,r)。例如计算 gcd(546, 429) 由于 5461(429)117 4293(117)78 1171(78)39 782(39) 因此 gcd(546, 429) gcd(429, 117) gcd(117, 78) gcd(78, 39) 39 该规则的证明我们不做过多解释感兴趣的同学可以看一下如何证明辗转相除法(欧几里德算法) - 知乎。我们只看基于该结论如何实现循环实现代码如下
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和它本身之外不能被任何其他自然数整除。其他数都是合数。比较特殊的是1即非素数也非合数。2是唯一的同时为偶数和素数的数字。 有了定义自然第一个问题就是如何判断一个正整数是否为素数。题目要求给定一个正整数n(n10^9)判断它是否为素数。 基本的方式是从2开始依次与n取余测试看看是否出现n%i0的情况如果出现了则说明当前的n能被i整除所以就不是。理论上一直测试到n-1假如都不是那就是素数了。 而事实上不需要测试这么多只要从2开始遍历一直到n^(1/2)就可以 不用执行到n-1。这个是有明确的数学证明的我们不再赘述如果不知道请回家问高中老师。所以实现代码就是
boolean isPrime(int num) {int max (int)Math.sqrt(num);for (int i 2; i max; i) {if (num % i 0) {return false;}}return true;}
基于该基础就可以造题了例如LeetCode204 给定整数 n 返回 所有小于非负整数 n 的质数的数量 。 示例1 输入n 10 输出4 解释小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。 这个问题几乎就是将上面的代码再套一层就行了直接遍历
public int countPrimes(int n) {int cnt 0;for (int i 2; i n; i) {if (isPrime(i)) {cnt;}}return cnt;
}
这个方法计算小的数据没有错但是计算比较大的n仍然会超时还是性能不够。我们下一节继续研究。
3 埃氏筛
上面LeetCode204 的题找素数的方法虽然能解决问题但是效率太低能否有效率更高一些的方法呢 解决这个题有一个有效的方法叫做埃氏筛后来又产生了线性筛 奇数筛等改进的方法。 基本思想是如果 x是质数那么大于 x 的 xy的倍数 2x. 3x… 一定不是质数因此我们可以从这一点入手。如下图所示: 我们先选中数字22是素数然后将2的倍数全部排除在数组里将该位置标记为0就行了。 接着我们选中数字33是素数然后将3的倍数全部排除。 接着我们选择数字55是素数然后将5的倍数全部排除。 接着我们选择 71113一直到n为什么 4 、6、8 、9 ...不会再选择了呢因为我们已经在前面的步骤中将其变成0了。所以实现代码如下
public int countPrimes(int n) {int[] isPrime new int[n];Arrays.fill(isPrime,1);int ans 0;for(int i2;in;i){if(isPrime[i]1){ans;if((long)i * in){for(int ji*i;in;ji){isPrime[j] 0;}}}}return ans;
}
这个是典型的以空间换时间的算法这种思想在解决一些问题的时候可以参考例如下面的丑数这个题。
4.丑数问题
这个是剑指offer中的题目我们把只包含质因子 2、3 和 5 的数称作丑数Ugly Number求按从小到大的顺序的第 n 个丑数。 示例 输入: n 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。 根据丑数的定义0 和负整数一定不是丑数。 当 n0 时若 n 是丑数则 n 可以写成 n 2^a 3^b 5^c 的形式其中 a,b,c 都是非负整数。特别地当 a,b,c 都是 000 时n1。 为判断 n 是否满足上述形式可以对 n 反复除以 2,3,5直到 n 不再包含质因数 2,3,5。若剩下的数等于 1则说明 n 不包含其他质因数是丑数否则说明n包含其他质因数不是丑数。 因此可以得到如下解答方式 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;}
本题也可以使用上面介绍的埃氏筛方式来解决 你可以思考一下如何做。
