凤舞凰扬 写道
elmar 写道
准备1-N之间的质数的集合
然后求每个质数的不大于N的最大幂,比如N=30时,2对应的最大幂是4。
然后最小公倍数就是所有质数的相应幂的积
比如N=10
小于10的质数有2,3,5,7
对应的最大幂是:3,2,1,1
则最小公倍数是:2^3x3^2x5^1x7^1 = 2520
不过这样做估计会很吃内存的
楼上列出的这个算法不错,比我前面想出的更好,不过我还是没有理解每个素数不大于N的最大幂所包含的数学原理。
这个算法和楼上的简单的算法的思路是一样的,只不过计算的过程有了变化。
凤舞凰扬 写道
虽然想到下面这个简单的算法,个人认为不算那么高效(因为需要对合数进行分解)。
1. 对于每个数,如果是素数,则一定是最小公倍数的构成,参与计算。如果是合数,则分解成一组素数。
2. 对于每个素数,都有一个类似map的结构(这种结构不仅仅是指语言的中map,而是类似的二维表),key为素数,value为素数出现的次数(可以是出现在自然数列中的,也可以是由合数分解出来的)。
3. 如果合数分解出的素数组存在于map中(key=素数,value>=分解的素数次数),则该合数不参与计算中。
数学原理解释:
1 这里应用了算术基本定理。
任何一个自然数N>1,都可以唯一的分解成质因数的连乘积,即
N=(P1^a1)*(P2^a2)......(Pn^an) (N>1)
其中P1,P2,P3,.......,Pn 为互不相等的质数且递增排列。
a1,a2,......,an 为自然数。
2 最小公倍数
整数m>1,n>1,如何求lcm(m,n)呢。
1 把m,n展开为标准的质数连乘积形式。
2 则lcm(m,n)的标准的质数连乘积形式中的质数必定来自于m或者n的标准的质数连乘积形式中的质数,其幂值为m,n中该质数对应的幂值的最大值。
例子
8=(2^3)
12=(2^2)(3^1)
lcm(m,n)=(2^3)(3^1)=24
扩展一下,如何求N个数的lcm呢。
1 把N个数展开为标准的质数连乘积形式。
2 则lcm的标准的质数连乘积形式中的质数必定来自于这N个数的标准的质数连乘积形式中的质数,其幂值为在这N个数的标准的质数连乘积形式中该质数对应的幂值的最大值。
例子
12=(2^2)(3^1)
10=(2^1)(5^1)
8=(2^3)
lcm=(2^3)(3^1)(5^1)=120
简单的总结一下这种算法的思路,就是确定lcm的质数因子和质数因子的幂指数。
对于leeldy的算法,其实和搂主的还是有一定区别的。
搂主的简单算法可以计算任意的连续整数的lcm。
而leeldy的算法只能计算从1开始的连续N个整数的lcm。
leeldy的算法中
因为是求1-N的连续的整数的lcm,所以1-N中的所有质数都在lcm的标准的质数连乘积中。
而求每个质数的不大于N的最大幂就是求该质数的幂指数了。
分享到:
相关推荐
在C#语言中,我们可以使用多种方法来计算两个自然数的最大公约数和最小公倍数。下面将详细介绍这两种计算方法。 ### 最大公约数 (GCD) #### 辗转相除法(欧几里得算法) 欧几里得算法是求最大公约数的经典方法,...
在C#编程中,求解两个自然数的最大公约数(Greatest Common Divisor, GCD)和最小公倍数(Least Common Multiple, LCM)是基础的数学算法问题,广泛应用于计算机科学,尤其是在处理整数操作时。下面将详细介绍如何...
//该代码描述了怎样求1到20的最小公倍数 #include using namespace std; int main() { int a[21]; for (int i = 0; i ; i++) { a[i] = i; } for (int i = 4; i ; i++) { for (int j = 2; j ; j++) { ...
1. Java不同数据类型变量的使用 ①定义不同的字符变量,依次给这些变量赋值:’A’,’2’,’猫’,’b’并输出结果;...2. 计算最小公倍数和最大公约数 ①定义两个整型变量m,n; ②计算最大公约数; ③最小公倍数;
7. 两个连续自然数的最大公约数是1,最小公倍数是它们的和。 8. 两个相邻奇数的最大公约数是1,最小公倍数是它们的乘积。 通过解决这些问题,我们可以加深对最大公因数和最小公倍数概念的理解,并学会如何在实际...
(2) “7和11没有最小公倍数”同样错误,因为任何两个不同的自然数都有一个唯一的最小公倍数,7和11的最小公倍数是77。(3) “1是所有非0自然数的公因数”是正确的,因为1能整除任何非零自然数。(4) “24和18的最小公...
这篇文档是针对五年级学生设计... - 短除法求最小公倍数,是通过连续除以共同的质因数来找到最小公倍数的方法。 这些练习题旨在帮助学生熟练掌握最小公倍数的概念和计算方法,通过解决实际问题来提升他们的数学能力。
例4:通过分解连续自然数的最小公倍数找出这三个数。 例5:通过年龄比例问题,结合公倍数和公约数概念,找出爷爷和小明的年龄。 同步演练题则进一步强化了这些技能的运用,包括找三个数的公约数和公倍数,以及解决...
- 对于任意两个自然数a和b,存在唯一的数c满足c是a和b的最小公倍数。 - 若a、b互质,则它们的最小公倍数等于ab。 #### 二、求最小公倍数的方法 1. **列举法**:将每个数的倍数一一列举出来,找到第一个共同出现...
2. **求最小公倍数的方法**: - 如果两个数互质(没有除了1以外的公因数),那么它们的乘积就是最小公倍数,如5和7。 - 如果其中一个数是另一个数的倍数,那么较大的数就是较小数的倍数,同时也是它们的最小公倍数...
本文将详细探讨如何使用编程方法计算两个正整数的最大公约数(Greatest Common Divisor, GCD)和最小公倍数(Least Common Multiple, LCM)。首先,我们来看如何用辗转相除法求最大公约数。 辗转相除法,也称为...
【短除法求最大公因数与最小公倍数】 短除法是一种常见的求解最大公因数(Greatest Common Divisor, GCD)和最小公倍数(Least Common Multiple, LCM)的方法,尤其在处理较大整数时非常实用。在小学数学中,分解质...
3. 短除法:通过连续除以相同的质因数,直到无法再除为止,最后的商乘以所有除数得到最小公倍数,而商的最小公约数就是最大公约数。 4. 辗转相除法(欧几里得算法):适用于较大的数,通过不断用较大的数除以较小的...
这是一个关于分数和等分的题目,需要找到10、12、15的最小公倍数,然后计算木棍被锯成的段数。 **练习五**: 1. 分别找出12、15、20的最小公倍数,计算木棍被锯成的段数。 2. 这是一个涉及步长和足迹重合的问题,...
2. **最小公倍数(Lowest Common Multiple, LCM)**:最小公倍数是若干个数共有的倍数中最小的一个。例如,4和6的最小公倍数是12。 3. **质数(Prime Number)**:质数是只有1和其本身两个正因数的自然数,如2、3、5等...
【最大公约数与最小公倍数】是小学六年级数学中的一个重要概念,涉及到数的整除性质和因数分解。最大公约数(Greatest Common Divisor, GCD)是指两个或多个非零整数共有约数中最大的一个,而最小公倍数(Least ...
训练五的问题是通过求不同等分的最小公倍数,计算木棍被锯成的小段数,以及父子两人步伐的重合点。 三、课后作业 作业中的问题延续了例题和训练的思路,需要学生运用最小公倍数的知识解决实际问题,例如糖果的分配...
写一个程序,对于给定的一个自然数N(1),和M个互不相同的十进制数字X1, X2,…,XM (M>=1), 找出N的一个最小的正倍数,使得该倍数中仅包含数字X1,X2,…,XM。 【输入形式】 输入文件为当前目录下的...
最大公因数是指几个数的公因数中的最大一个,而最小公倍数是指几个数的公倍数中的最小一个。了解最大公因数和最小公倍数的概念和性质,可以更好地解决相关的问题。 在应用最大公因数和最小公倍数方法时,需要先求出...