亲和数、相亲数
亲和数、相亲数
相亲数(Amicable Pair)，又称亲和数、友爱数，指两个正整数中，彼此的全部约数之和（本身除外）与另一方相等。
例如220与284：
220的全部约数(除掉本身)相加是：1+2+4+5+10+11+20+22+44+55+110=284
284的全部约数(除掉284本身)相加的和是：1+2+4+71+142=220
换句话说，亲和数又可以说成是两个正整数中，一方的全部约数之和与另一方的全部约数之和相等。
220的全部约数之和是：1+2+4+5+10+11+20+22+44+55+110+220 = 284+220 = 504
284的全部约数之和是：1+2+4+71+142+284 = 220+284 = 504
public static void main(String[] args)
int n = 1000000;
printLoveNumberGroup(n);
* 相亲数(Amicable Pair)，又称亲和数、友爱数，指两个正整数中，彼此的全部约数之和（本身除外）与另一方相等。
* http://zh.wikipedia.org/wiki/%E7%9B%B8%E4%BA%B2%E6%95%B0
* @param n
public static void printLoveNumberGroup(int n)
int m = 2;
Map&Integer, Boolean& map = new HashMap&Integer, Boolean&();
List&Integer& list = findYueSu(m);
int sum = getSum(list);
List&Integer& list2 = findYueSu(sum);
int sum2 = getSum(list2);
if (m == sum)
System.out.println("self sum["+ m +"]");
if (m == sum2)
if (null == map.get(Integer.valueOf(m)))
map.put(Integer.valueOf(sum), Boolean.TRUE);
System.out.println("love number["+ m +","+ sum +"]");
} while (m &= n);
* 查找被本身外的所有约数
* @param n
private static List&Integer& findYueSu(int n)
if (n & 1)
return java.util.Collections.emptyList();
List&Integer& list = new ArrayList&Integer&();
list.add(Integer.valueOf(1));
int mid = (int)Math.sqrt(n);
for (int i = 2; i &= i++)
int num = n/i;
if (i * num == n)
list.add(Integer.valueOf(i));
if (i != num)
list.add(Integer.valueOf(num));
private static int getSum(List&Integer& list)
int sum = 0;
if (null == list || list.isEmpty())
for (Integer num : list)
sum += num.intValue();第6课 寻找亲和数_百度文库
您的浏览器Javascript被禁用，需开启后体验完整功能，
享专业文档下载特权
&赠共享文档下载特权
&10W篇文档免费专享
&每天抽奖多种福利
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
第6课 寻找亲和数
阅读已结束，下载本文到电脑
定制HR最喜欢的简历
你可能喜欢扫二维码下载作业帮
3亿+用户的选择
下载作业帮安装包
扫二维码下载作业帮
3亿+用户的选择
至今为止发现几对亲和数,分别是多少,还会有么?
作业帮用户
扫二维码下载作业帮
3亿+用户的选择
亲和数是一种古老的数.遥远的古代,人们发现某些自然数之间有特殊的关系：如果两个数a和b,a的所有真因数之和等于b,b的所有真因数之和等于a,则称a,b是一对亲和数.据说,毕达哥拉斯(Pythagoras,希腊文Πυθαγρα,约前580年—前500年)的一个门徒向他提出这样一个问题：“我结交朋友时,存在着数的作用吗?”毕达哥拉斯毫不犹豫地回答：“朋友是你的灵魂的倩影,要象220和284一样亲密.”又说“什么叫朋友?就象这两个数,一个是你,另一个是我.”后来,毕氏学派宣传说：人之间讲友谊,数之间也有“相亲相爱”.从此,把220和284叫做“亲和数”或者叫“朋友数”或叫“相亲数”.这就是关于“亲和数”这个名称来源的传说.毕达哥拉斯首先发现220与284就是一对亲和数,在以后的1500年间,世界上有很多数学家致力于探寻亲和数,面对茫茫数海,无疑是大海捞针,虽经一代又一代人的穷思苦想,有些人甚至为此耗尽毕生心血,却始终没有收获.公元九世纪,伊拉克哲学、医学、天文学和物理学家泰比特·依本库拉曾提出过一个求亲和数的法则,因为他的公式比较繁杂,难以实际操作,再加上难以辨别真假,故它并没有给人们带来惊喜,或者走出困境.数学家们仍然没有找到第二对亲和数.直到费尔马(P．de Fermat,)才发现了另一对亲和数：1.十六世纪,已经有人认为自然数里就仅有这一对亲和数.有一些无聊之士,甚至给亲和数抹上迷信色彩或者增添神秘感,编出了许许多多神话故事.还宣传这对亲和数在魔术、法术、占星术和占卦上都有重要作用等等.距离第一对亲和数诞生2500多年以后,历史的车轮转到十七世纪,1636年,法国“业余数学家之王”费马找到第二对亲和数1,重新点燃寻找亲和数的火炬,在黑暗中找到光明.两年之后,“解析几何之父”——法国数学家笛卡尔(René Descartes)于日也宣布找到了第三对亲和数63584.费马和笛卡尔在两年的时间里,打破了二千多年的沉寂,激起了数学界重新寻找亲和数的波涛.在十七世纪以后的岁月,许多数学家投身到寻找新的亲和数的行列,他们企图用灵感与枯燥的计算发现新大陆.可是,无情的事实使他们省悟到,已经陷入了一座数学迷宫,不可能出现法国人的辉煌了.正当数学家们真的感到绝望的时候,平地又起了一声惊雷.1747年,年仅39岁的瑞士数学家欧拉竟向全世界宣布：他找到了30对亲和数,后来又扩展到60对,不仅列出了亲和数的数表,而且还公布了全部运算过程.欧拉采用了新的方法,将亲和数划分为五种类型加以讨论.欧拉超人的数学思维,解开了令人止步2500多年的难题,使数学家拍案叫绝.时间又过了120年,到了1867年,意大利有一个爱动脑筋,勤于计算的16岁中学生白格黑尼,竟然发现数学大师欧拉的疏漏——让眼皮下的一对较小的亲和数溜掉了.这戏剧性的发现使数学家如痴如醉.在以后的半个世纪的时间里,人们在前人的基础上,不断更新方法,陆陆续续又找到了许多对亲和数.到了1923年,数学家麦达其和叶维勒汇总前人研究成果与自己的研究所得,发表了1095对亲和数,其中最大的数有25位.同年,另一个荷兰数学家里勒找到了一对有152位数的亲和数.在找到的这些亲和数中,人们发现,亲和数发现的个数越来越少,数位越来越大.同时,数学家还发现,若一对亲和数的数值越大,则这两个数之比越接近于1,这是亲和数所具有的规律吗?人们企盼着最终的结论.电子计算机诞生以后,结束了笔算寻找亲和数的历史.有人在计算机上对所有100万以下的数逐一进行了检验,总共找到了42对亲和数,发现10万以下数中仅有13对亲和数.但因计算机功能与数学方法的不够,目前还没有重大突破,但是,寻找亲和数未来正等待着不畏艰辛的数学家和计算机专家,同时,发现新的亲和数的捷报也正等待着不畏艰辛的数学家和计算机专家.人们还发现每一对奇亲和数中都有3,5,7作为素因数.1968年波尔.布拉得利(P.Bratley)和约翰.迈凯(J.Mckay)提出：所有奇亲和数都是能够被3整除的.1988年巴蒂亚托(S.Battiato)和博霍(W.Borho)利用电子计算机找到了不能被3整除的奇亲和数,从而推翻了布拉得利的猜想.他找到了15对都不能被3整除的奇亲和数,最小的一对是：a=s*57199和 b=s*207其中s=5^4*7^3*11^3*13^2*17^2*19*61^2*97*107.将各个因数乘起来 a=和b=069375.它们都是36位大数.作为一个未解决的问题,巴蒂亚托等希望有人能找到最小的.另一个问题是是否存在一对奇亲和数中有一个数不能被3整除.还有一个欧拉提出的问题,是否存在一对亲和数,其中有一个奇数,另一个是偶数?因为现在发现的所有奇偶亲和数要么都是偶数,要么都是奇数.200多年来尚未解决.亲和数的研究主要有两方面：(1)寻找新的亲和数.(2)寻找亲和数的表达公式.关于后一项工作,早在9世纪,阿拉伯的学者泰比特(TabitibnQorra)就提出了一个构造亲和数的公式：如果三个数：p=3*2^(n-1)-1,q=3*2^n-1,r=9*2^(2n-1)-1都是素数,且p,q>2,则2^npq和2^nr就是一对亲和数.例如,取n=2,得p=5,q=11,r=71,则2^2*5*11=220和2^2*71=284是一对亲和数.
为您推荐：
其他类似问题
扫描下载二维码程序员编程艺术&第六章&求解500万以内的亲和数
本章陆续开始，除了继续保持原有的字符串、数组等面试题之外，会有意识的间断性节选一些有关数字趣味小而巧的面试题目，重在突出思路的“巧”，和“妙”。本章亲和数问题之关键字，“500万”，“线性复杂度”。
第一节、亲和数问题
题目描述：
求500万以内的所有亲和数
如果两个数a和b，a的所有真因数之和等于b,b的所有真因数之和等于a,则称a,b是一对亲和数。
例如220和284，，。
分析：首先得明确到底是什么是亲和数?
亲和数问题最早是由毕达哥拉斯学派发现和研究的。他们在研究数字的规律的时候发现有以下性质特点的两个数：
220的真因子是：1、2、4、5、10、11、20、22、44、55、110；
284的真因子是：1、2、4、71、142。
而这两个数恰恰等于对方的真因子各自加起来的和（sum[i]表示数i 的各个真因子的和），即
220=1+2+4+71+142=sum[284],
284=1+2+4+5+10+11+20+22+44+55+110=sum[220]。
得284的真因子之和sum[284]=220，且220的真因子之和sum[220]=284，即有sum[220]=sum[sum[284]]=284。
如此，是否已看出丝毫端倪?
如上所示，考虑到1是每个整数的因子，把出去整数本身之外的所有因子叫做这个数的“真因子”。如果两个整数，其中每一个真因子的和都恰好等于另一个数，那么这两个数，就构成一对“亲和数”（有关亲和数的更多讨论，可参考这：）。
了解了什么是亲和数，接下来咱们一步一步来解决上面提出的问题（以下内容大部引自水的原话，同时水哥有一句原话，“在你真正弄弄懂这个范例之前，你不配说你懂数据结构和算法”）。
看到这个问题后，第一想法是什么？模拟搜索+剪枝？回溯？时间复杂度有多大？其中bn为an的伪亲和数，即bn是an的真因数之和大约是多少？至少是10^13（@iicup：N^1.5 对于5*10^6 , 次数大致 10^10 而不是 10^13.）的数量级的。那么对于每秒千万次运算的计算机来说，大概在1000多天也就是3年内就可以搞定了（iicup的计算: 10^13 / 10^7 =1000000(秒) 大约 278 小时. ）。如果是基于这个基数在优化，你无法在一天内得到结果的。
一个不错的算法应该在半小时之内搞定这个问题，当然这样的算法有很多。节约时间的做法是可以生成伴随数组，也就是空间换时间，但是那样，空间代价太大，因为数据规模庞大。
在稍后的算法中，依然使用的伴随数组，只不过，因为题目的特殊性，只是它方便和巧妙地利用了下标作为伴随数组，来节约时间。同时，将回溯的思想换成递推的思想（预处理数组的时间复杂度为logN（调和级数）*N，扫描数组的时间复杂度为线性O（N）。所以，总的时间复杂度为O（N*logN+N）（其中logN为调和级数））。
第二节、伴随数组线性遍历
依据上文中的第3点思路，编写如下代码：
//求解亲和数问题
//第一个for和第二个for循环是logn（调和级数）*N次遍历,第三个for循环扫描O（N）。
//所以总的时间复杂度为O（n*logn）+O（n）=O（N*logN）（其中logN为调和级数）。
//关于第一个for和第二个for寻找中，调和级数的说明：
//比如给2的倍数加2，那么应该是n/2次，3的倍数加3应该是n/3次，...
//那么其实就是n*（1+1/2+1/3+1/4+...1/(n/2)）=n*（调和级数）=n*logn。
//copyright@上善若水
//July、updated，。
#include&stdio.h&
intsum[5000010];//为防越界
for(i=0;i&=5000000;i++)
sum[i]=1;//1是所有数的真因数所以全部置1
for(i=2;i+i&=5000000;i++)//预处理，预处理是logN（调和级数）*N。
//@litaoye：调和级数1/2+1/3+1/4......的和近似为ln(n)，
//因此O(n*(1/2+1/3+1/4......))=O(n*ln(n))=O(N*log(N))。
//5000000以下最大的真因数是不超过它的一半的
j=i+i;//因为真因数，所以不能算本身，所以从它的2倍开始
while(j&=5000000)
//将所有i的倍数的位置上加i
sum[j]+=i;
for(i=220;i&=5000000;i++)//扫描，O（N）。
//一次遍历，因为知道最小是220和284因此从220开始
if(sum[i]&i&&sum[i]&=5000000&&sum[sum[i]]==i)
//去重，不越界，满足亲和
printf("%d%d/n",i,sum[i]);
//求解亲和数问题 //第一个for和第二个for循环是logn（调和级数）*N次遍历,第三个for循环扫描O（N）。 //所以总的时间复杂度为 O（n*logn）+O（n）=O（N*logN）（其中logN为调和级数）。 //关于第一个for和第二个for寻找中，调和级数的说明： //比如给2的倍数加2，那么应该是 n/2次，3的倍数加3 应该是 n/3次，... //那么其实就是n*（1+1/2+1/3+1/4+...1/(n/2)）=n*（调和级数）=n*logn。 //copyright@ 上善若水 //July、updated，。 #include&stdio.h& int sum[5000010]; //为防越界 int main() { int i, for (i = 0; i &= 5000000; i++) sum[i] = 1; //1是所有数的真因数所以全部置1 for (i = 2; i + i &= 5000000; i++) //预处理，预处理是logN（调和级数）*N。 //@litaoye：调和级数1/2 + 1/3 + 1/4......的和近似为ln(n)， //因此O(n *(1/2 + 1/3 + 1/4......)) = O(n * ln(n)) = O(N*log(N))。 { //5000000以下最大的真因数是不超过它的一半的 j = i + //因为真因数，所以不能算本身，所以从它的2倍开始 while (j &= 5000000) { //将所有i的倍数的位置上加i sum[j] += j += } } for (i = 220; i &= 5000000; i++) //扫描，O（N）。 { // 一次遍历，因为知道最小是220和284因此从220开始 if (sum[i] & i && sum[i] &= 5000000 && sum[sum[i]] == i) { //去重，不越界，满足亲和 printf("%d %d/n",i,sum[i]); } } return 0; }
运行结果：
@上善若水：
1、可能大家理解的还不是很清晰，我们建立一个5 000 000 的数组，从1到2 500 000 开始，在每一个下标是i的倍数的位置上加上i，那么在循环结束之后，我们得到的是什么？是 类似埃斯托拉晒求素数的数组（当然里面有真的亲和数），然后只需要一次遍历就可以轻松找到所有的亲和数了。时间复杂度，线性。
2、我们可以清晰的发现连续数据的映射可以通过数组结构本身的特点替代，用来节约空间，这是数据结构的艺术。在大规模连续数据的回溯处理上，可以通过转化为递推生成的方法，逆向思维操作，这是算法的艺术。
3、把最简单的东西运用的最巧妙的人，要比用复杂方法解决复杂问题的人要头脑清晰。
第三节、程序的构造与解释
我再来具体解释下上述程序的原理，ok，举个例子，假设是求10以内的亲和数，求解步骤如下：
因为所有数的真因数都包含1，所以，先在各个数的下方全部置1
然后取i=2,3,4,5（i&=10/2），j依次对应的位置为j=（4、6、8、10），（6、9）,（8）,（10）各数所对应的位置。
依据j所找到的位置，在j所指的各个数的下面加上各个真因子i（i=2、3、4、5）。
整个过程，即如下图所示（如sum[6]=1+2+3=6，sum[10]=1+2+5=8.）：
1 2 3 4 5 6 7 8 9 10
1 1 1 1 1 1 1 1 1 1
然后一次遍历i从220开始到5000000，i每遍历一个数后，
将i对应的数下面的各个真因子加起来得到一个和sum[i]，如果这个和sum[i]==某个i’，且sum[i‘]=i，
那么这两个数i和i’，即为一对亲和数。
i=2；sum[4]+=2，sum[6]+=2，sum[8]+=2，sum[10]+=2，sum[12]+=2...
i=3，sum[6]+=3，sum[9]+=3...
i=220时，sum[220]=284，i=284时，sum[284]=220；即sum[220]=sum[sum[284]]=284，
得出220与284是一对亲和数。所以，最终输出220、284，...
litaoye专门为本亲和数问题开帖子继续阐述，有兴趣的朋友可继续参见：。同时，任何人对本亲和数问题有任何问题，也可以回复到上述帖子上。
//求解亲和数问题
//copyright@litaoye
//July、胡滨，updated，。
usingSystem.Collections.G
namespaceCSharpTest
classProgram
publicstaticvoidMain()
intmax=5000000;
DateTimestart=DateTime.N
int[]counter=CreateCounter(max);
for(inti=0;i&counter.Li++)
intnum=counter[i]-i;
//if(num&counter.Length&&num&i&&counter[num]==counter[i])
//Console.WriteLine("{0}{1}",i,num);
Console.WriteLine((DateTime.Now-start).TotalSeconds);
Console.ReadKey();
staticint[]CreateCounter(intn)
List&int&primes=newList&int&();
int[]counter=newint[n+1];
counter[1]=1;
for(inti=2;i&=n;i++)
if(counter[i]==0)
counter[i]=i+1;
primes.Add(i);
for(intj=0;j&primes.Cj++)
if(primes[j]*i&n)
if(i%primes[j]==0)
intl=primes[j]*primes[j];
while(k%primes[j]==0)
l*=primes[j];
k/=primes[j];
counter[primes[j]*i]=counter[k]*(l-1)/(primes[j]-1);
counter[primes[j]*i]=counter[i]*(primes[j]+1);
测试结果：
单位second。
//求解亲和数问题 //copyright@ litaoye //July、胡滨，updated，。 using S using System.Collections.G namespace CSharpTest { class Program { public static void Main() { int max = 5000000; DateTime start = DateTime.N int[] counter = CreateCounter(max); for (int i = 0; i & counter.L i++) { int num = counter[i] - //if (num & counter.Length && num & i && counter[num] == counter[i]) // Console.WriteLine("{0} {1}", i, num); } Console.WriteLine((DateTime.Now - start).TotalSeconds); Console.ReadKey(); } static int[] CreateCounter(int n) { List&int& primes = new List&int&(); int[] counter = new int[n + 1]; counter[1] = 1; for (int i = 2; i &= i++) { if (counter[i] == 0) { counter[i] = i + 1; primes.Add(i); } for (int j = 0; j & primes.C j++) { if (primes[j] * i & n) if (i % primes[j] == 0) { int k = int l = primes[j] * primes[j]; while (k % primes[j] == 0) { l *= primes[j]; k /= primes[j]; } counter[primes[j] * i] = counter[k] * (l - 1) / (primes[j] - 1); } else counter[primes[j] * i] = counter[i] * (primes[j] + 1); } } } } } /* 测试结果： 0...46875 单位second。 */
Copyright (C) , All Rights Reserved.
版权所有 闽ICP备号
processed in 0.045 (s). 13 q(s)握住科学钥匙 打开科学之门
寻找亲和数
人与人之间讲究友情，而有趣的是，数与数之间也有相类似的关系，数学家把一对存在特殊关系的数称为“亲和数”。亲和数，又称相亲数、友爱数、友好数，指两个正整数中，彼此的全部约数之和（本身除外）与另一方相等。
那么什么是亲和数呢？亲和数是一种古老的数，在遥远的古代，人们发现某些自然数之间有特殊的关系：如果两个数a和b，a的所有除本身以外的因数之和等于b，b的所有除本身以外的因数之和等于a，则称a和b是一对亲和数。亲和数的基本定理是，对任一个正整数z，因数分解后可以表达为以下的形式z=ambn?cl，其中：a，b，c为素数；m，n，l为大于或等于1的正整数。
320年左右，古希腊毕达哥拉斯发现的220与284，是人类认识的第一对亲和数。1636年，法国数学家费马发现了第二对亲和数1。两年之后，“解析几何之父”——法国数学家笛卡尔于日宣布找到了第三对亲和数63584。费马和笛卡尔在两年的时间里，打破了二千多年的沉寂，激起了数学界重新寻找亲和数的波涛。
而数学家欧拉曾找出59对新的亲和数。在以后的半个世纪的时间里，人们在前人的基础上，不断更新方法，陆陆续续又找到了许多对亲和数。到了1923年，数学家麦达其和叶维勒汇总前人研究成果与自己的研究所得，发表了1095对亲和数，其中最大的数有25位。同年，另一位荷兰数学家里勒找到了一对有152位数的亲和数。在计算机出现后，人们加快了亲和数的寻找。
亲和数是较为稀少的数，到现在还不能确定亲和数对的数量是否有限。在搜寻出的亲和数对中，均同为偶数或奇数，还没有一奇一偶的情况，但这是否是普遍规律，还未见证明。亲和数的分布有较好的规律性，在搜索范围增加到原来的10倍时，亲和数对的数量为原来的2倍多，随着范围增大，亲和数越稀少，搜索也越困难。假设增长比率为a，按a=2.3计算，以1亿为计算起点，则100亿亿(1018)内的亲和数对估计为231×2.310=956952；以100亿为计算起点，则估计为=1089305，差别不大，估计为100万对左右。在该搜索范围内平均万亿个数才能找到一对亲和数，由此可见其寻找难度。
另外，采用分解算法，寻找到1万亿以上的5对亲和数：(1 000 452 085 744,1 023 608 366 096)，(1 000 539 285 525,1 015 331 690 475)，(1 000 607 505 404,1 147 934 333 956)，(1 001 352 481 250, 1 117 674 392 350)，(1 001 583 011 750,1 019 368 284 250)，可见在该范围内，平均约搜索3亿个数才发现一对亲和数。
本作品为“科普中国-科学原理一点通”原创，转载时务请注明出处。
作者： 高一之
[责任编辑: 李浩]
数学,亲和数