Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

Efektywny algorytm na sumę dzielników właściwych danej liczby

Ostatnio zmodyfikowano 2021-01-18 22:10
Autor Wiadomość
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
P-177986
pekfos
» 2021-01-18 21:22:03
https://en.wikipedia.org/wiki/Integer_factorization
Faktoryzacja jest tu najtrudniejszym obliczeniowo elementem, więc nie próbuj uzyskać od razu wszystkich dzielników, a raczej wszystkie czynniki pierwsze. Złożone dzielniki możesz skonstruować później.
P-177987
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?
P-177988
pekfos
» 2021-01-18 21:58:10
https://math.stackexchange.com/questions/163245/finding-sum-of-factors-of-a-number-using-prime-factorization
https://www.amansmathsblogs.com/factors-formula-how-to-find-sum-of-factors-of-composite-numbers/
Bez podziału na czynniki pierwsze raczej nie da rady. Skoro masz przeszukać przedział, to może zamiast rozbijać liczby powinieneś je konstruować? Analogicznie do sita Eratostenesa.
P-177989
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
P-177990
« 1 »
  Strona 1 z 1