1. 亲密数对查找程序概述
亲密数对(Amicable Numbers)是数论中一个有趣的概念,它指的是一对满足特定条件的正整数。具体来说,如果整数A的所有真因子(即除了自身之外的所有约数)之和等于整数B,同时整数B的所有真因子之和又等于整数A,并且A < B,那么这对数(A,B)就被称为亲密数对。
最著名的例子是220和284这对数:
- 220的真因子:1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110,其和为284
- 284的真因子:1, 2, 4, 71, 142,其和为220
这个程序的主要功能是让用户输入一个正整数n,然后找出所有小于n的亲密数对。程序采用C语言编写,使用了穷举法作为核心算法,通过嵌套循环和条件判断来实现亲密数对的查找。
提示:亲密数对在数学上也被称为"友好数对",这个概念最早可以追溯到毕达哥拉斯时代,具有悠久的历史和数学意义。
需要模型API调用? 免费领10W Token,多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 程序设计与实现细节
2.1 程序整体结构
程序的结构可以分为以下几个主要部分:
- 用户界面:显示程序功能和亲密数定义的说明
- 输入处理:获取用户输入的查找范围上限n
- 核心算法:通过嵌套循环查找亲密数对
- 结果输出:格式化输出找到的亲密数对
- 程序收尾:等待用户按键退出
这种结构设计使得程序逻辑清晰,各功能模块分工明确,便于理解和维护。
2.2 核心算法实现
程序的核心算法采用穷举法,具体实现步骤如下:
- 外层循环遍历1到n-1的所有整数a
- 对于每个a,计算其所有真因子之和b
- 对于得到的b,计算其所有真因子之和m
- 检查是否满足m == a且a < b的条件
- 如果满足,则输出这对亲密数(a,b)
这种算法虽然时间复杂度较高(约为O(n²)),但对于n不是特别大的情况(比如n ≤ 100,000)是完全可行的,而且实现简单直观。
2.3 关键代码解析
让我们仔细分析程序中的几个关键代码段:
真因子求和部分:
c复制for(b=0,i=1;i<=a/2;i++)
if(!(a%i))b+=i;
这段代码计算整数a的所有真因子之和:
- 初始化b为0,i从1开始
- 循环条件i <= a/2是因
