首页 > 代码库 > 5.20亲密数
5.20亲密数
Q:若整数A的全部因子(包括1,不包括本身)之和等于B,并且整数B的全部因子之和等于A,则称A与B是亲密数。求解3000以内的全部亲密数。
思路:先将1~3000以内所有数的全部因子之和算出来,存入到数组x[]中,这样x[i]中存放的是i的因子之和,寻找{1,2,……3000}范围中所有的亲密数的算法 如下:
for(i=1;i<=3000;i++) //将1~3000所有数的因子和 放在一个数组x[1,2^3000]中 if(i没找到其亲密数,即i在集合B中) { for(j=i+1;j<=3000;j++) if(j为i的亲密数) 输出亲密数(i,j),并记录j已经找到其亲密数; }
全部代码如下:
#include <iostream> using namespace std; int factorsum(int a) {//求a的因子和 int sum=0; for(int i=1;i<a;i++) if(a%i==0) sum+=i; return sum; } int isfriend(int a,int b,int i,int j) {//判断a与b是否是亲密数,若是亲密数就返回1,否则返回0 if(a==j && b==i) return 1; else return 0; } void friendly() { int i,j,x[3001]; for(i=1;i<=3000;i++) //将1~3000所有数的因子和 放在一个数组x[]中,省去了每次都要重复计算每个数的因子之和 x[i]=factorsum(i); for(i=1;i<=3000;i++) { if(x[i]!=-111) { for(j=i+1;j<=3000;j++) if(isfriend(x[i],x[j],i,j)) { printf("(%d,%d) ",i,j); x[j]=-111;//表示j已经找到亲秘数 } } } } int main() { friendly(); return 0; }
5.20亲密数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。