I00039 亲密数（Amicable numbers）

本文主要是介绍I00039 亲密数（Amicable numbers），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一个正整数a的所有正因子之和等于b，b的所有正因子之和等于a，其中因子包括1但不包括本身，且a不等于b，则称a，b为亲密数对。

问题描述：输入n（n为int类型），计算输出≤n的所有亲密数对，亲密数对的两个数用“..”连接，例如：220..284，每个亲密数对之间用空格隔开，输出在一行里。

问题分析：可以使用筛选法原理计算各个数的因子之和，然后再判定输出。

程序说明：数组sum[]中存放除了自身之外的因子之和，例如sum[i]中存放除了i以外的i的因子之和。

AC的C语言程序如下：

/* I00039 亲密数（Friend number） */#include <stdio.h>
#include <memory.h>#define MAXN 40000000int sum[MAXN+1];void maketable(int n)
{memset(sum, 0, sizeof(sum));sum[1] = 0;int i=2, j;while(i<=n) {sum[i]++;j = i + i;      /* j=ki, k>1 */while(j <= n) {sum[j] += i;j += i;}i++;}
}int main(void)
{int n, flag, i;scanf("%d", &n);maketable(n);flag = 0;for(i=1; i<=n; i++)if(sum[i] <= n && i < sum[i] && sum[sum[i]] == i) {if(flag)printf(" ");flag = 1;printf("%d..%d", i, sum[i]);}printf("\n");return 0;
}

运行实例：

100000
220..284 1184..1210 2620..2924 5020..5564 6232..6368 10744..10856 12285..14595 17296..18416 63020..76084 66928..66992 67095..71145 69615..87633 79750..88730

这篇关于I00039 亲密数（Amicable numbers）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---