问题:给定一个N,求其所有约数之和。
分析:先证明一个质数p的指数形式pa 的所有约数之和为σ(pa) = (pa+1 ? 1)/(p ? 1),其中σ(pa) 表示一个数的所有约数之和
因为σ(pa) = 1 + p + p2 + ... + pa..................
对上式乘以p可得:pσ(pa) = p + p2 + p3 + ... + pa + 1
两式相减可得:pσ(pa)-σ(pa) = (p-1)σ(pa) = pa+1 - 1
即:σ(pa) = (pa+1 - 1)/(p - 1)。
又有性质 σ(a×b×...)=σ(a)×σ(b)×...,其中a,b,...互质。
接下来,对于一个N,我们总可以把N分解为若干个质数的指数形式相乘,问题得到了很好地解决。
分享到:
相关推荐
输出m,n的最大公约数和最小公倍数,大家共同学习。
输入两个正整数m和n,求其最大公约数和最小公倍 数。
求m和n的最小公倍数和最大公约数 用于求m和n 的最小公倍数和最大公约数的C#源代码
输入两个正整数m和n,求其最大公约数和最小公倍数输入两个正整数m和n,求其最大公约数和最小公倍数输入两个正整数m和n,求其最大公约数和最小公倍数输入两个正整数m和n,求其最大公约数和最小公倍数输入两个正整数m...
欧几里德算法,俗称求m,n最大公约数,使用java实现,在网上看其他的都是用其他语言实现的。
求n个整数的最大公约数,n由键盘输入。代码简单易懂。
用JAVA写了个关于两个数最大公约数最小公倍数的程序..不晓得质量如何import java.util.*; public class dd { ... System.out.println("最大公约数:"+n); System.out.println("最小公倍数:"+s); } }
递归求n 个数最大公约数和用辗转相除法求最大公约数
求两个正整数m、n的最大公约数 Java语言实现
约数之和: (p1^0 + p1 ^ 1 + … p1^a1) * (p2^0 + p2 ^ 1 + …p2^a2) … 求几个数的乘积的约数之和 #include #include #include #include using namespace std; const int mod = 1e9 + 7; int n; long long ans = 1...
现在Hankson认为自己已经熟练地掌握了这些知识,他开始思考一个“求公约数”和“求公倍数”之类问题的“逆问题”,这个问题是这样的:已知正整数a0,a1,b0,b1,设某未知正整数x满足: 1、x和a0的最大公约数是a1。 2、x...
比较简单,才学习java但是看见有一些求最大公约数的方法比较繁琐所以自己写一个小程序和大家分享。
python 输入两个正整数计算最大公约数和最小公倍数 示例
整数m和n的最大公约数记为GCD(m, n)。 最小公倍数(Least Common Multiple,简称LCM)是指两个或多个整数共有的倍数中除了0以外最小的一个。整数m和n的最小公倍数记为LCM(m, n)。 整数m、n、GCD(m, n)以及LCM(m, n)...
用C++实现,先求两个数的最大公约数,然后递归。
包含:1、辗转相除法函数嵌套盒图2、辗转相除法函数递归盒图3、穷举法求最小公倍数盒图4、穷举法求最大公约数流程图
。。。
这是清华大学潭浩强的一个错误,希望对大家有所帮助
java 欧几里德算法、连续整数检测算法
VB 求多个数的最大公约数,这应该是个比较... r = m Mod n '辗转相除法求最大公约数 If r = 0 Then Exit Do '找到最大公约数后即退出 m = n n = r Loop big = n '返回这两个数的最大公约数 End Function