Sposob na wyznaczenie dzielnikow n!, inny niz naiwny

Sposob na wyznaczenie dzielnikow n!, inny niz naiwny
Blue_Carpet
  • Rejestracja: dni
  • Ostatnio: dni
  • Postów: 132
0

Witam,
Czy ktos moglby podpowiedziec o czym warto przeczytac lub w jaki sposob mozna napisac algorytm, ktory bedzie dobry i efektywny, na wyznaczenie wszystkich dzielnikow danej silnii?
Np.: 5!
Najprostsze co mi przychodzi do głowy to wymnożenie tzn. 234*5 = 120 i znalezienie wszystkich dzielnikow 120, ale taki sposob jest tzn. "naiwny" i mało optymalny więc odpada.

LukeJL
  • Rejestracja: dni
  • Ostatnio: dni
  • Postów: 8536
2

a nie możesz wziąć wszystkich liczb (5! => 1, 2, 3, 4, 5) i znaleźć dzielniki tych wszystkich liczb od 1 do 5, wsadzić do tablicy, a potem zlikwidować duplikaty?

Ale uwaga - nie wiem czy to poprawne rozwiązanie ani nawet, jeśli poprawne, to nie wiem czy to optymalne, czy też dość naiwne, więc sam musisz sprawdzić.

camed_
  • Rejestracja: dni
  • Ostatnio: dni
  • Lokalizacja: Białystok
  • Postów: 41
2

Rozbij n! na czynniki pierwsze. Np. z 7! zrób 23225237*. Wtedy będziesz mógł już łatwo znaleźć poszczególne dzielniki.

bogdans
  • Rejestracja: dni
  • Ostatnio: dni
2

Ja bym robił tak, każdą liczbę z przedziału [2,n] rozkładam na czynniki pierwsze, liczę ile razy pojawił się każdy czynnik, np. dla 8! dostajemy

Kopiuj
2  7
3  2
5  1
7  1

Każdy dzielnik dostajemy wybierając liczby nie przekraczające krotności czynnika, w podanym przykładzie jest 832*2 = 96 dzielników, każdy ma postać 2a*3b*5c*7d, 0<=a<=7, 0<=b<=3 0<=b<=2, 0<=c<=1, 0<=d<=1

Zarejestruj się i dołącz do największej społeczności programistów w Polsce.

Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.