Решение задачи №371 «Дружественные числа» с ACMP
Условие задачи
Два различных натуральных числа называются дружественными, если первое из них равно сумме делителей второго числа, за исключением самого второго числа, а второе равно сумме делителей первого числа, за исключением самого первого числа. Требуется найти все пары дружественных чисел, оба из которых принадлежат промежутку от M до N.
Входные данные
Входной файл INPUT.TXT в первой строке содержит натуральные числа M и N, разделенные пробелом, не превышающие 106.
Выходные данные
В выходной файл OUTPUT.TXT выведите в каждой строке по паре чисел через пробел. Первое число пары должно быть меньше второго. Строки должны быть отсортированы в порядке возрастания первого числа пары. Если пар дружественных чисел в промежутке нет, то следует вывести "Absent".
Решение на C++
#include<iostream>
#define M 1000000
using namespace std;
int main (){
int m,n,i,j,k,c=0; int a[M+1];
for(i=2;i<=M;++i)a[i]=1;
for(i=2;i<=M/2;++i)
for(j=i+i;j<=M;j+=i)
a[j]+=i;
cin>>m>>n;
for(i=m;i<=n;i++){k=a[i];
if(k>=m&&k<=n&&a[k]==i&&i<k){c++;
cout<<i<<' '<<k<<endl;}}
if(c==0)cout<<"Absent";
return 0;}
Условия задач взяты с сайта acmp.ru