例:如果整数A的全部因子(不包括A)之和等于B,且整数B的全部因子(不包括B)之和等于A,则将A和B称为亲密数,如220的全部因子(不包括220)之和:1+2+4+5+10+11+20+22+44+55+110等于284,284的全部因子(不包括284)之和:1+2+4+71+142等于220,故220和284为亲密数。求10000以内的所有亲密数。
分析:
变量: 要判断的整数 i,i 的全部因子j之和sum1,sum1的全部因子k之和sum2 要进行的操作: ①将1~10000循环遍历,判断某个数 i 的全部因子(可联想到素数判断),并求和sum1 ②判断sum1的全部因子,并求和sum2 ③判断 i 和sum2是否相等,若相等,则它们为亲密数,输出(输出判断隐含条件:亲密数是不等的两个数,且“A与B”和“B与A”是一样的,只要输出一个,即“相互输出取其一,按序”)
核心算法:
求某个数的全部因子(不包括这个数本身):穷举法,用数 i 对1~i-1之间的所有数取余,看余数是否为0(即i%j==0(1<=j<i)),如果为0,则说明该数是i的因子
#include<stdio.h> int main() { int i,j,k,sum1,sum2; for(i=1;i<=10000;i++)//对10000以内的数进行穷举 { sum1=0; sum2=0; for(j=1;j<i;j++)//判断1~i-1内的数j是否为i的因子 if(i%j==0) sum1+=j;//i的所有因子求和 for(k=1;k<sum1;k++)//判断1~sum1-1内的数k是否为sum1的因子 if(sum1%k==0) sum2+=k;//sum1的所有因子求和 if(sum2==i&&i<sum1)//“A与B”和“B与A”是一样的,只要输出一个 printf("%5d与%5d是亲密数\n",i,sum1) } return 0; }