Oto bardzo głupi sposób:
def divisorGenerator(n):
for i in xrange(1,n/2+1):
if n%i == 0: yield i
yield n
Wynik, który chciałbym uzyskać, jest podobny do tego, ale chciałbym mądrzejszego algorytmu (ten jest zbyt wolny i głupi :-)
Potrafię wystarczająco szybko znaleźć czynniki pierwsze i ich krotność. Mam generator, który generuje czynnik w ten sposób:
(współczynnik1, krotność1)
(współczynnik2, krotność2)
(współczynnik3, krotność3)
i tak dalej ...
czyli wyjście
for i in factorGenerator(100):
print i
jest:
(2, 2)
(5, 2)
Nie wiem, na ile jest to przydatne w tym, co chcę robić (zakodowałem to pod kątem innych problemów), w każdym razie chciałbym mądrzejszego sposobu
for i in divisorGen(100):
print i
wyślij to:
1
2
4
5
10
20
25
50
100
AKTUALIZACJA: Wielkie dzięki dla Grega Hewgilla i jego "sprytnego sposobu" :) Obliczenie wszystkich dzielników na 100000000 zajęło mu 0,01s wobec 39-tych, które głupi sposób objął moją maszynę, bardzo fajnie: D
UPDATE 2: Przestań mówić, że to duplikat tego postu. Obliczenie liczby dzielników podanej liczby nie wymaga obliczania wszystkich dzielników. To inny problem, jeśli myślisz, że tak nie jest, poszukaj opcji „Divisor function” na Wikipedii. Przeczytaj pytania i odpowiedź przed wysłaniem, jeśli nie rozumiesz, jaki jest temat, po prostu nie dodawaj nieprzydatnych i już udzielonych odpowiedzi.
Odpowiedzi:
Biorąc pod uwagę twoją
factorGenerator
funkcję, otodivisorGen
co powinno działać:Ogólna wydajność tego algorytmu będzie zależeć całkowicie od wydajności
factorGenerator
.źródło
Aby rozwinąć to, co powiedział Shimi, powinieneś uruchamiać pętlę tylko od 1 do pierwiastka kwadratowego z n. Następnie, aby znaleźć parę, zrób
n / i
, a to obejmie całą przestrzeń problemu.Jak również zauważono, jest to problem NP lub „trudny”. Wyczerpujące wyszukiwanie, sposób, w jaki to robisz, jest prawie tak dobre, jak to tylko możliwe, aby uzyskać gwarantowane odpowiedzi. Ten fakt jest wykorzystywany przez algorytmy szyfrowania i tym podobne, aby pomóc je zabezpieczyć. Gdyby ktoś miał rozwiązać ten problem, większość, jeśli nie cała nasza obecna „bezpieczna” komunikacja byłaby niepewna.
Kod Pythona:
Który powinien wyświetlić listę taką jak:
źródło
Chociaż rozwiązań tego jest już wiele, naprawdę muszę to opublikować :)
Ten jest:
Kod:
źródło
while i*i <= nn
przezwhile i <= limit
, gdzielimit = math.sqrt(n)
Myślę, że możesz się zatrzymać
math.sqrt(n)
zamiast n / 2.Podam ci przykład, abyś mógł to łatwo zrozumieć. Teraz
sqrt(28)
jest5.29
takceil(5.29)
będzie 6. Więc jeśli zatrzymam się na 6, to otrzymam wszystkie dzielniki. W jaki sposób?Najpierw zobacz kod, a następnie zobacz obrazek:
Teraz zobacz poniższy obrazek:
Powiedzmy, że dodałem już
1
do mojej listy dzielników i zacznę odi=2
takTak więc pod koniec wszystkich iteracji, gdy dodałem iloraz i dzielnik do mojej listy, wypełnione są wszystkie dzielniki 28.
Źródło: jak określić dzielniki liczby
źródło
math.sqrt(n) instead of n/2
jest obowiązkowy dla elegancjiPodoba mi się rozwiązanie Grega, ale chciałbym, żeby było bardziej podobne do Pythona. Wydaje mi się, że byłoby to szybsze i bardziej czytelne; więc po pewnym czasie kodowania wyszedłem z tego.
Dwie pierwsze funkcje są potrzebne do stworzenia iloczynu kartezjańskiego list. I może być ponownie użyty, gdy tylko pojawi się ten problem. Swoją drogą sam musiałem to zaprogramować, jeśli ktoś zna standardowe rozwiązanie tego problemu to zapraszam do kontaktu.
„Factorgenerator” zwraca teraz słownik. Następnie słownik jest wprowadzany do „dzielników”, którzy używają go do generowania najpierw listy list, gdzie każda lista jest listą czynników postaci p ^ n z p liczbą pierwszą. Następnie tworzymy iloczyn kartezjański tych list i na koniec używamy rozwiązania Grega do wygenerowania dzielnika. Sortujemy je i zwracamy.
Przetestowałem go i wydaje się, że jest nieco szybszy niż poprzednia wersja. Przetestowałem go jako część większego programu, więc nie mogę powiedzieć, o ile jest szybszy.
Pietro Speroni (pietrosperoni dot it)
PS Po raz pierwszy wysyłam post do stackoverflow. Z niecierpliwością czekam na wszelkie uwagi.
źródło
Oto sprytny i szybki sposób na zrobienie tego dla liczb do i około 10 ** 16 w czystym Pythonie 3.6,
źródło
Zaadaptowano z CodeReview , oto wariant, który działa
num=1
!źródło
NameError: global name 'prime_factors' is not defined
. Żadna z pozostałych odpowiedzi ani pierwotne pytanie nie określa, co to robi.Dodam tylko nieco poprawioną wersję Anivartha (ponieważ uważam, że jest najbardziej pytoniczna) do wykorzystania w przyszłości.
źródło
Stare pytanie, ale oto moje podejście:
Możesz proxy za pomocą:
UWAGA: W przypadku języków, które obsługują, może to być rekurencyjne.
źródło
Zakładając, że
factors
funkcja zwraca czynniki n (na przykładfactors(60)
zwraca listę [2, 2, 3, 5]), oto funkcja obliczająca dzielniki n :źródło
Oto moje rozwiązanie. Wydaje się, że to głupie, ale działa dobrze ... i próbowałem znaleźć wszystkie właściwe dzielniki, więc pętla zaczęła się od i = 2.
źródło
Jeśli zależy Ci tylko na używaniu list składanych i nic innego nie ma dla Ciebie znaczenia!
źródło
Jeśli twój komputer ma mnóstwo pamięci, brutalna pojedyncza linia może być wystarczająco szybka dzięki numpy:
Zajmuje mniej niż 1s na moim wolnym komputerze.
źródło
Moje rozwiązanie za pomocą funkcji generatora to:
źródło
źródło
U mnie to działa dobrze i jest również czyste (Python 3)
Niezbyt szybko, ale zwraca dzielniki linia po linii tak, jak chciałeś, możesz także zrobić list.append (n) i list.append (liczba), jeśli naprawdę chcesz
źródło