Efektywny algorytm na sumę dzielników właściwych danej liczby
Ostatnio zmodyfikowano 2021-01-18 22:10
gonskabalbinka Temat założony przez niniejszego użytkownika |
Efektywny algorytm na sumę dzielników właściwych danej liczby » 2021-01-18 21:06:02 Witam mam do napisania program w którym będę musiał znaleźć sumę dzielników dużej liczby naturalnej (liczba jest typu unsigned long long) Wiem, że jest algorytm naiwny on się nie sprawdzi. Można ograniczyć liczbę iteracji przy szukaniu dzielników do n/2 lub sqrt(n), ale te ograniczenia też nie przechodzą testów. Może ktoś podać linka albo wyjaśnić jaki jest skuteczny i szybki algorytm na policzenie tej sumy |
|
pekfos |
» 2021-01-18 21:22:03 |
|
gonskabalbinka Temat założony przez niniejszego użytkownika |
» 2021-01-18 21:39:19 W zasadzie problem jest inny, ale sprowadza się do szukania dzielników liczby. Mam zadanie z codewars. Wyszukać tzw buddy pairs w podanym zakresie. Buddy pairs zdefiniowano jako: załóżmy, że s(n) to suma dzielników właściwych liczby n. Liczbę n i m nazwiemy buddy pairs gdy s(n)=m+1 i s(m)=n+1. Nie wiem jak to rozgryźć, nie wiem czy jest jakaś formuła matematyczna, bo szukanie dzielników dla liczby unsigned long long zawsze przekroczy limit czasu. Czy w tym przypadku faktoryzacja zadziała? |
|
pekfos |
» 2021-01-18 21:58:10 |
|
gonskabalbinka Temat założony przez niniejszego użytkownika |
» 2021-01-18 22:10:10 Dzięki za odpowiedzi. Długo się już męczę z tym zadaniem. Może faktoryzacja coś pomoże. Zobaczymy |
|
« 1 » |