首页 > 代码库 > 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亲密数