Решение задачи №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