C++ : Project Euler: Problem 21 usando a STL (list)


Problem 21
05 July 2002

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a  b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284.
The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.



    Primeiro, criamos a função properDivisors(int num), que calcula a soma dos divisores de um número (exceto ele mesmo).
    Depois, a função d(int n) checa o se o valor de n e properDivisors(n) são um par de amicable.

    Aqui encontramos uma pedra no caminho.
    Se primeiro testarmos 220, teremos que 220 e 284 são pares e serão adicionados.
    Porém, ao testar 284, teremos que 284 e 220 são pares e serão novamente adicionados.

    Vamos contornar esse problema usando a STL (Standard Template Library), usando uma lista, a pairList.
    Ela será global. Cada vez que formos testar um números, primeiro devemos checar se ele nao esta na lista.
    Só depois de nos certificarmos que ele não está é que iremos testar se ele forma um amicable.
    Dentro da funçao d(): 'n==j', quer dizer que os números formam um par e que 'n != i' diz que eles não são iguais.

    Para testar se o numero nao esta na lista, usamos a funçao bool testList()
    Ela retorna true, caso o numero estenja na lista e false se nao estiver

    Na função main, ao percorremos de 1 até  10.000, antes de começarmos vamos testar se o dito cujo número esta na lista.
    Assim, ele só vai pra função d() se não estiver.

    Ao final, somamos todos os números que se encontram na lista


------------------------------------------------ 21.cpp
#include <iostream>
#include <list>
using namespace std;

list<int> pairList;
list<int>::iterator iter;

int properDivisors(int num)
{
    int count,
        sum=0;

    for(count=1 ; count <= num/2 ; count++)
    {
        if(num % count == 0)
                sum=sum+count;

    }
            return sum;
}

bool testList(int num)
{
    for(iter = pairList.begin() ; iter != pairList.end() ; iter++)
        if(*iter == num)
            return true;

    return false;
}

int d(int n)
{
    int i,
        j;

    i = properDivisors(n);
    j = properDivisors(i);

    if(n == j && n != i)
        {
            cout<<"d("<<n<<") : "<<i<<endl;
            pairList.push_back(n);
        }
}

int main()
{
    int num,
        sum=0;

    for(num=1 ; num<=10000 ; num++)
        if(! testList(num) )
            d(num);

    for(iter = pairList.begin() ; iter != pairList.end() ; iter++)
                sum+=*iter;

        cout<<endl<<"Soma : "<<sum<<endl;
 }