[Goglez]

Załóżmy że mam listę liczb pierwszych od 2 do sqrt(n) za darmo. Która metoda faktoryzacji dowolnej liczby n będzie szybsza, GNFS czy sprawdzanie wszystkich liczb pierwszych po kolei?
Chodzi mi o szybkość w kontekście złożoności obliczeniowej, nie rzeczywistej implementacji.

#algorytmy #informatyka #programowanie #matematyka

[sezzart]

@Goglez: ilosc liczb pierwszych jest szacowana jako \theta(n/(loglog n)). wiec pod wzgledem zlozonosci, lista liczb pierwszych nie rozni sie duzo od listy wszystkich liczb od 1 do sqrt(n)