Liczby zaprzyjaźnione <1000000

Question

Cześć, mam za zadanie zrobić program do szukania liczb zaprzyjaźnionych mniejszych od miliona.

Oto mój kod:

#Zadanie 11. Napisać program wyszukujący liczby zaprzyjaźnione mniejsze od miliona.

for y in range (1,1000001):
    k = y-1
    suma1  = 0
    while k>0 :
        if y%k==0:
            suma1+=k
        k-=1
    for x in range (y,1000000):
        p = x - 1
        suma2 = 0
        while p > 0:
            if x % p == 0:
                suma2 += p
            p -= 1
        if suma1==x and suma2==y and x!=y:
            print("Znalazłem parę liczb zaprzyjaźnionych:",x,y)

I tutaj moje pytanie: co zrobić aby program wykonał zadanie szybciej? 

Answer 1

Druga pętla `for x in range (y,1000000)` jest niepotrzebna. Wiesz, że jedyną sensowną drugą liczbą do pary jest suma dzielników pierwszej liczby. Wystarczy sprawdzić, czy właściwość sprawdza się też w drugą stronę.

Comments

Bonusowa rada: żeby policzyć sumę dzielników (lub ogólnie, zbiór dzielników) liczby N, nie musisz się iterować N razy - da się znacznie mniej :)

Z tymi radami, mój kod pokazuje wszystkie w mniej niż minutę.

---

Bardzo dziękuję za pomoc :)