Bueno, ante todo no conozco Fortran ni lo he usado nunca, pero en tu código, no tendrías que poner a 0 las variables
s y
t para cada nuevo valor de
n?
Otra cosa, por lo que veo, tú quieres encontrar los números amigos en un intervalo [
n,
m] y en tu código lo que haces es iterar sobre el valor de
n y lo comparas con
m, que la dejas fija. Así, suponiendo que lo que te he dicho arriba esté bien, sólo miras si
m es amigo de algún número dentro del intervalo, pero si el intervalo es [30,50], no miras nunca si 34 es amigo de 42, por poner un ejemplo.
Una forma de corregir el algoritmo sería hacer lo siguiente (te lo pongo en pseudocódigo):
i := n;
mientras i <= m
s := suma_divisores(i);
si s > i y s <= m
t := suma_divisores(s);
si t = i
imprime i " y " s " son amigos";
fsi
fsi
i := i + 1;
fsi
Con este algoritmo, la complejidad es del orden de O(n
2) puesto que tal y como tú calculas los divisores necesitas otro bucle lineal para cada número. En C++, el código quedaría así más o menos (no lo he probado):
#include <iostream>
using namespace std;
int suma_div(int n) {
int s = 0;
for (int i = 1; i <= n/2; ++i) if (n%i == 0) s += i;
return s;
}
int main() {
int n, m;
cin >> n >> m;
for (int i = n; i <= m; ++i) {
int s = suma_div(i);
if (s > i and s <= m and suma_div(s) == i) cout << i << " y " << s << " son amigos" << endl;
}
}
Para mejorar la eficiencia, podrías hacer una Criba de Eratóstenes al inicio del código para calcular todos los primos hasta la raíz cuadrada de
m y luego para calcular los divisores, factorizar con dichos primos el número y generar con un pequeño bactracking todos los divisores, pero aunque supongo que iría más rápido, el código sería un poco más largo.
Autor
En línea
.
