相亲数环

* 整合重组与分解转化是数据处理相辅相成的手段与技巧 *；

整数通过巧妙整合重组为若干有特殊意义的数或数组，是培养与检验程序设计技能的重要方面；

数学大师毕达哥拉斯早年发现，220与284两数之间存在这奇妙的联系：

220的真因数之和为：1+2+4+5+10+11+20+22+44+55+110=284；
284的真因数之和为：1+2+4+71+142=220；

毕达哥拉斯把这样的数对a，b称为相亲数对：a的真因数（小于本身的因数）之和为b，而b的真因数之和为a；

相亲数对的直接推广是相亲数环：呈连环套形式的多个相亲数构成相亲数环；

例如，a真因数之和为b，b的真因数之和为c，c的真因数之和为d，d的真因数之和又为a，则a、b、c、d称为一个4节相亲数环；

数学界对探寻相亲数对与相亲数环的热情不减；

4位以内相亲数对

试探寻4位以内即区间 [1，9999] 中的相亲数对；

1.说明：

对指定4位以内的每一个整数i应用试商实施枚举判别，根据相亲数的定义，用试商法 i%j=0 找出i的所有小于i的真因数j，并求出真因数的和s；

然后用相同的方法找出整数s的真因数之和s1；

如果有s1=i，则i、s为相亲数对；

为减少试商循环次数，注意到数i若为非平方数，它的大于1小于i的因数成对出现，每一对中较小因数要小于i的平方根；

这样试商j循环只要从2取到i平方根t=sqrt（i），可大大减少j循环次数，缩减程序的运行时间；

若数 i 恰为整数t的平方，此时t为i的一个因数而不是一对，因而在和s中减去多加的因数t；

找到相亲数对，统计对数并打印输出；

2.程序设计：

#include<stdio.h> #include<math.h> int main() { int i,j,m,s,t,s1; m=0; for(i=1;i<=9999;i++) { s=1; t=(int)sqrt(i); for(j=2;j<=t;j++); if(i%j==0) s=s+j+i/j; if(i==t*t) /*求i的真因数之和s*/ s-=t; if(i<s) /*规定i<s,避免重复*/ { s1=1; t=(int)sqrt(s); for(j=2;j<=t;j++) if(s%j==0) s1=s1+j+s/j; if(s==t*t) /*求s的真因数之和s1*/ s1-=t; if(s1==i) /*条件判断*/ { m++; printf("相亲数对%d: %d,%d\n",m,i,s); } } } printf("4位以内的相亲数对共以上%d组\n",m); }

3.程序运行示例及其注意事项：

相亲数对 1: 220 , 284 相亲数对 2: 1184,1210 相亲数对 3: 2620,2924 相亲数对 4: 5020,5564 相亲数对 5: 6232,6368 4位以内的相亲数对共以上5组

注意：由输出结果可知，3位以内只有毕达哥拉斯发现的唯一一对相亲数；

n节相亲数环

所谓n（n>2）节相亲数环，是指n个数满足以下关系：

a1的真因数之和为a2，a2的真因数之和为a3，……，最后an的真因数之和为a1；

这样，a1，a2，a3，……，an形成一个n节相亲数环，

1.说明：

设置数组s： s（0）即为递增枚举循环中选取的整数i（i从11开始递增取值），其真因数之和存储到s（1）。一般地，通过k循环实现把s（k-1）的真因数之和存储到s（k）（k为1~n）；

判别：若s（n）！=s（0），则试下一个i，直至s（n）=s（0）时，找到相亲数的n个环数，进行打印输出后退出；

若数i增至约定的还未搜索到n节相亲数环，即行退出；

2.程序设计：

#include<stdio.h> #incldue<math.h> int main() { int c,k,n; long i,j,t,s[100]; printf("搜索n节相亲环数，请输入n:"); scanf("%d",&n); i=10; while(1) { i++; s[0]=i; s[n]=i+1; /*初始化s[0]!=s[n]*/ for(c=0,k=1;k<=n;k++) { s[k]=1; t=(int)sqrt(s[k]-1); for(j=2;j<=t;j++) /*求s[k-1]的因数之和*/ if(s[k-1]%j==0) s[k]=s[k]+j+s[k-1]/j; if(s[k-1]==t*t) s[k]-=t; for(j=0;j<=k-1;j++) if(s[k]==s[j]) { c=1; break; } if(c==1) break; } if(s[0]==s[n]) /*满足n环首尾相等，输出解*/ { printf("搜索到%d节相亲数环:",n); for(k=0;k<=n-1;k++) printf(" %ld",s[k]); printf("\n"); return; } if(i>) { printf("尚未搜索到%d节相亲数环!\n"); return; } } }

3.程序运行示例及其注意事项：

搜索n节相亲数环，请输入n:4 搜索到4节相亲数环:    搜索n节相亲数环，请输入n:5 搜索到5节相亲数环:12496 14288 15472 14536 14264

注意：如果需要具体给出相亲数环中的每一个数的真因数，程序应如何修改？

今天的文章相亲数环分享到此就结束了，感谢您的阅读。

4位以内相亲数对

n节相亲数环

相关推荐