Sposob na wyznaczenie dzielnikow n!, inny niz naiwny

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.

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ć.

2

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

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

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

1 użytkowników online, w tym zalogowanych: 0, gości: 1