[Resolvido] Problema complicado de resolver

[Vinicius_Zibetti_Res]

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.

Translated by translate.google.com:

Deixe d (n) ser definido como a soma dos divisores de n (números menores que n que dividem uniformemente em n).
Se d (a) = b e d (b) = a, onde a ≠ b, então a e b são um par amigável e cada um de a e b são chamados de números amigáveis​​.

Por exemplo, os divisores de 220 ​​são 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 e 110, portanto d (220) = 284. Os divisores de 284 são 1, 2, 4, 71 e 142, assim d (284) = 220.

Avaliar a soma de todos os números amigáveis ​​com 10 mil.

Meu código é o seguinte:

package Problem21;

import java.util.*;

public class AmicableN {
	public static void main(String[] args) {
		AmicableN a = new AmicableN();
		List<Integer> aux = new LinkedList<Integer>();
		for (int i = 1; i < 10000; i++) {
			for (int j = 1; j < 10000; j++) {
				if (i != j) {
					if (!aux.contains(i + j)) {
						if (a.isAmicable(i, j)) {
							aux.add(i + j);
						}
					}

				}
			}
		}
		int ret = 0;
		for (int i : aux) 
			ret += i;

		System.out.println(ret);
	}

	public boolean isAmicable(int a, int b) {
		int auxa = this.sumDivisors(a);
		int auxb = this.sumDivisors(b);
		if (auxa == b && auxb == a) {
			return true;
		}
		return false;
	}

	public int sumDivisors(int a) {
		int ret = 0;
		for (int i = 1; i < a; ++i) {
			if (a % i == 0) {
				ret += i;
			}
		}
		return ret;
	}
}

Mas este meu código esta demorando demais para calcular, alguem teria uma solução mais trivial ?

[Markus_Alemao]

Saudações …

Então …inseri um metodo que verifica se o numero é primo (o que reduz significativamente as iterações no loop) acho que dessa forma voce reduz o tempo em ± 50%:

import java.util.*;

public class AmicableN {
	public static void main(String[] args) {
		AmicableN a = new AmicableN();
		ArrayList<Integer> aux = new ArrayList<Integer>();
		for (int i = 1; i < 1000; i++) {
			for (int j = 1; j < 1000; j++) {
				if (i != j) {
					if (!aux.contains(i + j)) {
						if (a.isAmicable(i, j)) {
							aux.add(i + j);
						}
					}

				}
			}
		}
		int ret = 0;
		for (int i : aux) 
			ret += i;

		System.out.println(ret);
	}

	public boolean isAmicable(int a, int b) {
		return (this.sumDivisors(a) == b && this.sumDivisors(b) == a);
	}
	public boolean isPrimo(int a){
		boolean primo = false;
		if(a%2 ==1){
			primo = true;
			long limite = (long) Math.sqrt(a);  
			for(int i = 3; i<limite; i+=2){
				if(a % i==0){
					primo = false;
					break;
				}
			}
		} 
		return primo;
	}


	public int sumDivisors(int a) {
		int ret = 0;
		if(isPrimo(a)){
			return a;
		}
		for (int i = 1; i < a; ++i) {
			if (a % i == 0) {
				ret += i;
			}
		}
		return ret;
	}
}

[ViniGodoy]

Outra forma de agilizar é perceber que se A é amigável com B, então B também é amigável com A.
No seu código você está testando as duas coisas.

[Vinicius_Zibetti_Res]

[quote=ViniGodoy]Outra forma de agilizar é perceber que se A é amigável com B, então B também é amigável com A.
No seu código você está testando as duas coisas.[/quote]

Viny, eu acho que o que voce disse não tem muita relação, pelo motivo:
20 = 1, 2, 4, 5, 10 = 22
22 = 1, 2, 11 = 14

A unica forma de eu verificar se um numero é amigavel com o outro é fazendo as duas verificações.

Ou eu não entendi muito bem o que voce tentou explicar…
Mas obrigado, este algoritmo, com o "Crivo" ficou menos custoso mesmo, mas mesmo assim ainda muito lento.
Por favor mais soluções.

Só a correção aqui, o isPrimo(int n) -> return 1;
Por que ele quer numeros menos do que "n", se for primo a soma dos divisores menores do q ele é "1".

[ViniGodoy]

Então, no seu exemplo, vc está testando se 20 é amigável com 22:
20 = 1, 2, 4, 5, 10 = 22
22 = 1, 2, 11 = 14

E não é. Então, pq mais para frente vc testa se 22 é amigável com 20? Você já sabe que não é.

Da mesma forma, se 220 é amigável com 284, não tem pq testar se 284 é amigável com 220.

[ViniGodoy]

Me parece que seria bem mais rápido vc montar um array com as somas dos divisores para números menores que 10.000, e depois testar se são amigáveis baseados nesse array. Isso evitaria calcular constantemente a soma para números que você já calculou alguma vez.

Veja a besteira que vc está fazendo:
Se vc estiver em i = 100, vc calcula os divisores de 100 a cada j. E calcula outra vez quando o j é 100. Isso irá consumir uma quantidade enorme de tempo.

[ViniGodoy]

Outra coisa. Vc pode criar um método sumDivisors que receba a soma do número já calculado. Dessa forma, você pode abortar o processo de soma assim que ela for maior que o número calculado.

Por exemplo, se a soma dos divisores de A for 10, não tem pq vc continuar somando os divisores de B se vc obter uma soma > 10.
E uma correção. O método isPrime deve retornar 1 na soma dos divisores, não a. O único divisor de um primo, sem o próprio primo, é 1.

Além disso, lembre-se que o maior divisor de X é X/2.

Finalmente, lembre-se que o método contains de um list tem performance de O(n). O ideal seria vc usar ali um hashSet, que tem performance de O(1).

Ainda com todas essas otimizações, acho que minha idéia anterior é mais rápida, mas o ideal é colocar as duas juntas e testar. Geralmente caches perdem desempenho no acesso a memória, e nem sempre são tão rápidos quanto imaginamos.

[ViniGodoy]

Bom, levei mais tempo para confirmar que essa era a resposta certa, do que para elaborar o programa em si:

[code]public class Euler21 {
public static void main(String[] args) {
long before = System.currentTimeMillis();
int divisors[] = new int[10000];
for (int i = 1; i < 10000; ++i)
divisors[i] = sumDivisors(i, divisors);

	int sum = 0;
	for (int i = 1; i < 10000; ++i)
		for (int j = i+1; j < 10000; ++j)
			if (divisors[i] == j && divisors[j] == i)
				sum += (i+j);
	long elapsed = System.currentTimeMillis() - before;
	System.out.printf("A soma é %d calculada em %d ms.", sum, elapsed);
}

private static int sumDivisors(int num, int[] divisors) {
	int sum = 1;
	for (int i = 2; i <= num/2; i++)
		if (num % i == 0)
			sum += i;
	
	return sum;
}

}[/code]

[ViniGodoy]

O mesmo código acima comentado:

[code]public class Euler21 {
public static void main(String[] args) {
long before = System.currentTimeMillis();
//Primeiro calculamos todas as somas de divisores.
//Isso evitará fazer o cálculo das somas para um mesmo número 2x
int divisors[] = new int[10000];
for (int i = 1; i < 10000; ++i)
divisors[i] = sumDivisors(i, divisors);

	//Com todas as somas em mãos, fica fácil testar quem é amicable.
	int sum = 0;
	for (int i = 1; i < 10000; ++i)
		//observe que j começa em i+1.
		//Assim grantimos que não testamos j == i ou o par de maneira invertida, 
		//por exemplo, (20 e 22), e em outro momento, (22 e 20)
		for (int j = i+1; j < 10000; ++j) 
			if (divisors[i] == j && divisors[j] == i)
				sum += (i+j);
	
	long elapsed = System.currentTimeMillis() - before;
	System.out.printf("A soma é %d calculada em %d ms.", sum, elapsed);
}

private static int sumDivisors(int num, int[] divisors) {
	int sum = 1;
	//Observe que não é necessário testar depois da metade de num.
	for (int i = 2; i <= num/2; i++)
		if (num % i == 0)
			sum += i;
	
	return sum;
}

}[/code]

[entanglement]

Usando as dicas do Vinigodoy (se bem que não conferi se está certo - não estou conseguindo validar minha senha no site do Project Euler):

class AmicableNumbers {
    public static void main (String[] args) {
		// Achando a soma dos divisores - processo um pouco lento :)
		long t = System.currentTimeMillis();
		int[] sumDivisors = new int[10001];
		for (int i = 1; i <= 10000; ++i) {
			for (int j = 1; j <= i / 2; ++j) {
				if (i % j == 0) {
					sumDivisors[i] += j;
				}
			}
		}
		// Achando os números amigos
		int sum = 0;
		for (int a = 1; a <= 10000; ++a) {
			int b = sumDivisors [a];
			if (b <= 10000 && sumDivisors [b] == a && a < b) {
//				System.out.printf ("%d - %d%n", a, b);
				sum += a + b;
			}
		}
		System.out.printf ("sum = %d - found in %d ms%n", sum, System.currentTimeMillis() - t);
	}
}

[pmlm]

Optimizando ainda mais:

public class AmicablePair{  
    private static final int MAX = 10000;
    
    public static void main(String[] args) { 
        long startTime = System.currentTimeMillis();
        int divisors[] = new int[MAX];  
        int sum = 0;

        for (int i = 1; i < MAX; i++){
            if (divisors[i] != 0){
                continue;
            }
            sum += check(i, divisors);
        }  
                      
        long endTime = System.currentTimeMillis();
        System.out.println("Soma: " + soma + " em " + (endTime-startTime)+"ms");
    }  
      
    private static int check(int i, int[] divisors){
        if (divisors[i] == 0) {
            divisors[i] = sumDivisors(i);
        }
        
        if (i == divisors[i]||divisors[i] >= MAX || divisors[divisors[i]] != 0){
            return 0;
        }
        
        divisors[divisors[i]] = sumDivisors(divisors[i]);
                
        if (i == divisors[divisors[i]]){
            return i + divisors[i];
        }
        
        return check(divisors[i], divisors);
    }
      
    private static int sumDivisors(int num) {  
        int sum = 1;  
        for (int i = 2; i < (num/2+1); i++)  
            if (num % i == 0)  
                sum += i;  
              
        return sum;  
    }  
}  

[Vinicius_Zibetti_Res]

Olá, obrigado pelas respostas, e um obrigado especial para o Vinigodoy por ter postado tantas possibilidades e exclareciemtnos sobre este probleminha matematico…
Eu tava pensando em usar uma programacao dinamica, mas como n sei implementar, tava chupando o dedo. Obrigado aew galera…