liczby zaprzyjaźnione mniejsze od 1 000 000

0

Hej! Mam problem z programem wypisującym pary liczb zaprzyjaźnionych mniejszych od miliona.

Liczby zaprzyjaźnione to para różnych liczb naturalnych, takich że suma dzielników właściwych (mniejszych od tej liczby) każdej z tych liczb równa się drugiej. Pierwszą parą takich liczb, która została podana już przez Pitagorasa, jest para liczb 220 i 284, ponieważ:

220 = 1 + 2 + 4 + 71 + 142 (dzielniki 284)
284 = 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 (dzielniki 220)
Nie wiadomo, czy istnieje nieskończenie wiele par liczb zaprzyjaźnionych i czy istnieje taka para liczb o różnej parzystości.

Tutaj mój kod:

#include <iostream>

using namespace std;

int main()
{
int i, j;
int suma1=1, suma2=1;                        //sumy dzielników, od razu równe 1, bo 1 dzieli każdą liczbę

for(int i=1; i<=1000000; i++)                   // pierwsza liczba(?)
{
    for(int k=2; k<=500000; k++)             // spawdzanie kolejnych dzielników liczby, sprawdzam do 500 000
        {
        if(1000000%k==0) suma1=suma1+k;             //jeśli to dzielnik, to dodaję jego wartość do sumy
        }
}

for(int j=1; j<=500000; j++)                   // druga liczba(?)
{                                         //analogicznie jak w pierwszym przypadku
    for(int m=2; m<=500000; m++)
        {
        if(1000000%m==0) suma2=suma2+m;
        }
}
if (suma1==j && suma2==i) cout<< i <<" i " << j << endl;     //czy mogę tak porównać?
    return 0;
}

Program nie działa (otwiera się tylko konsola i kursor sobie miga). Chyba coś jest nie tak z tym zmiennymi w iteracjach, nie wiem czy można je tak porównywać (ostatni warunek), bo to w sumie dzieje się poza tymi iteracjami już. Jakieś wskazówki, uwagi? :)

PS. Chciałam to zrobić na razie bez tablic, jeśli się da :)

3

o_O a napisz to moze w wersji dla człowieka? Czemu nie napiszesz najpierw funkcji "znajdź dzielniki właściwe" a potem dopiero pisz resztę algorytmu bazując na niej? Bo teraz robisz jakieś głupie copypasty i w ogóle nie wiadomo co chcesz osiągnąć.
Co więcej szukasz tych dzielników w sposób iście tragiczny. Zauważ na przykład że jeśli k jest dzielnikiem liczby n to n/k także nim jest! Np. dla liczby 10 jeśli znajdujesz dzielnik 2 to automatycznie wiesz też że 10/2 = 5 jest dzielnikiem. Dwa w cenie jednego! Co więcej automatycznie nie ma sensu szukać dzielników większych od pierwiastka z danej liczby, bo te powyżej pierwiastka dostaniemy właśnie dzięki takiemu parowaniu. I nagle zamiast O(n) masz O(sqrt(n)) w zasadzie bez wysiłku.
Jeśli musisz "bez tablic" to napisz funkcje która od razy sumuje te dzielniki, ale trudniej to będzie debugować, bo jak masz listę to od razu widać że np. jakichś liczb ci brakuje albo coś dublujesz.

Ale idźmy trochę dalej z twoim problemem -> zauważ ze mamy tutaj pewne własności podobne do programowania dynamicznego. Bo jeśli znam sumę dzielników liczby n to jednocześnie znasz praktycznie "za darmo" sumę dzielników każdej liczby k*n bo jeśli k było na liscie dzielników to suma wynosi tyle samo co dla n a jeśli k nie było na liscie dzielników to suma dla k*n to jest w rzeczywistości tyle co suma przecięcia zbiorów dzielników dla n i dla k. No ale tutaj to już wypadałoby trzymać sobie te wartości w jakimś set<T> żeby wygodnie na tym operować.

1 użytkowników online, w tym zalogowanych: 0, gości: 1