东方博宜OJ 1140：亲密数对 ← 约数的成对性

【题目来源】https://oj.czos.cn/p/1140【题目描述】键盘输入 NN 在 2 至 2000 之间求 2 至 N 中的亲密数对就是 A 的因子和等于 BB 的因子和等于 A且 A≠B。如 48 和 75 是亲密数对。48 的因子和为 2346812162475而 75 的因子和为 35152548。【输入格式】只有一行为一个整数 N2≤N≤2000​​​​​​​【输出格式】输出若干行每行两个整数用一个空格隔开。​​​​​​​【输入样例】200【输出样例】48 7575 48140 195195 140​​​​​​​【数据范围】请注意求出的亲密数对的 2 个数都不应该超过 n 的范围。【算法分析】●什么是约数设 ab 为整数且 b≠0。若存在整数 k使得 ak×b。则称 b 是 a 的约数因数记作 b|a。●约数的成对性对于任意整数 x如果 i 是 x 的约数那么 x/i 也是 x 的约数。证明已知 i 是 x 的约数故 x/i 是整数。又因为 x/(x/i)i 为整数故根据约数定义知 x/i 是 x 的约数。●推论若 x 存在大于 1 的约数则一定存在一个不超过 sqrt(x) 的约数。约数成对性在素数判定中的应用假设 x 是合数则存在一对约数 (a,b)使得 a×bx2≤a≤b。显然可由 a×a≤a×bx^2 推出 a≤sqrt(x)即合数 x 必然存在一个不超过 sqrt(x) 的真约数。所以在素数判定问题中只需要遍历 2 到 sqrt(x) 之间有没有能整除 x 的数就行不用一直遍历到 x-1。● 关键点说明题目不包含 1 作为因子只统计除自身外大于 1 的约数。【算法代码一】#include bits/stdc.h using namespace std; int factorSum(int x) { int sum0; for(int i2; i*ix; i) { if(x%i0) { sumi; if(i!x/i) { sumx/i; } } } return sum; } int main() { int n; cinn; for(int a2; an; a) { int bfactorSum(a); if(bn) continue; int tfactorSum(b); if(ta a!b) { couta bendl; } } return 0; } /* in: 200 out: 48 75 75 48 140 195 195 140 */【算法代码二】#include bits/stdc.h using namespace std; int factorSum(int x) { int sum0; for(int i2; i*ix; i) { if(x%i0) { sumi; if(i!x/i) { sumx/i; } } } return sum; } int main() { int n; cinn; for(int a2; an; a) { for(int b2; bn; b) { int safactorSum(a); int sbfactorSum(b); if(sab sba a!b) { couta bendl; } } } return 0; } /* in: 200 out: 48 75 75 48 140 195 195 140 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/161994231https://blog.csdn.net/hnjzsyjyj/article/details/161995534https://blog.csdn.net/liunian_curry/article/details/139721281