iloczyn liczb ktuś: jak rozwiązać takie zadanie: iloma zerami kończy się iloczyn liczb od 1 do 1962 włącznie?

ICSP: a z iloczynu jakich liczb mogą wziąć się te zera ?

ktuś: kończących się na 5 i 2, albo na 10 i drugiej dowolnej

ICSP: ale 10 = 5*2 czyli wystarczy policzyć ile w tej liczbie będzie 5 ponieważ 2 jest znacznie więcej.

ktuś: nie rozumiem dlaczego tak...

ICSP: 0 na końcu biorą się z iloczynu liczb 5 * 2 1962! = 1 * 2 * 3 * 4 * ... * 1962 = 1 * 2 * 3 * 2² * 5 * (2*3) * ... * 1962 Jak widzisz dwójek zawsze będzie więcej. Jak policzysz ile jest piątek to dostaniesz liczbę 0 na końcu.

ktuś: no dobra, to chyba kumam, ale co z liczbami kończącymi się na 10?

ICSP: 10 = 2*5 iloczyn 2 i 5 daje 0

ICSP: na końcu oczywiscie.

Trivial: Chodzi o rozkład na liczby pierwsze. Dwójek jest dużo więcej niż piątek, tak jak napisał ICSP. Piątki zdarzają się co pięć liczb. Interesują nas właśnie te liczby: 5, 10, 15, 20, 25, 30, 35, ..., 1960 Są one postaci: k*5, gdzie k = 1, 2, ..., 392 W tych liczbach, co pięć będzie miało podwójną piątkę: 5². Są to liczby postaci k*25, gdzie k = 1, 2, ..., 78 Znowu, co pięć z tych nowych liczb będzie miało czynnik 5³. Są to: k*125, gdzie k = 1, 2, .., 15 Podobnie: k*625, gdzie k = 1, 2, 3. Odpowiedź: tych zer jest 3 + 15 + 78 + 392 = 488. Sprawdźmy: Prelude> length . takeWhile (=='0') . reverse . show . product $ [1..1962] 488

ktuś: i tak nie wiem czemu tak, ale dzięki

Trivial: Dlaczego nie wiesz? Każdy czynnik iloczynu rozkładamy na liczby pierwsze, np.: 2 → 2 3 → 3 4 → 2² 5 → 5 6 → 2*3 7 → 7 8 → 2³ 9 → 3² 10 → 2*5 11 → 11 12 → 2²*3 13 → 13 14 → 2*7 15 → 3*5 Itd.... Zera na końcu to ilość 10 w tym iloczynie. Ale 10 nie jest liczbą pierwszą. 10 = 2*5. Czyli trzeba policzyć ile jest dwójek i piątek po rozkładzie na liczby pierwsze w liczbie 1962!. Mniejsza ilość (dwójek lub piątek) jest liczbą dziesiątek. Jak wcześniej było zauważone, dwójek jest więcej niż piątek, więc wystarczy policzyć piątki. Wszystkie liczby w iloczynie 1*2*3*...*1962, które w rozkładzie mają piątkę to: 5, 10, 15, 20, ....., 1960 (jest ich 1960/5 = 392) Niektóre z nich mają w swoim rozkładzie dwie piątki. Trzeba to uwzględnić. Są to liczby: 25, 50, 75, 100, ..., 1950 (jest ich 1950/25 = 78) Następnie, niektóre w rozkładzie mają trzy piątki: 125, 250, 375, ..., 1875 (jest ich 1875/125 = 15) Wreszcie, nieliczne mają w rozkładzie cztery piątki: 625, 1250, 1875. (jest ich 3) Żeby policzyć wszystkie piątki dodajemy: 3 + 15 + 78 + 392 = 488. Tyle jest piątek w liczbie 1962!. Dwójek jest więcej, zatem jest również 488 dziesiątek, które utworzą zera na końcu.

Mila: I po co komu potrzebne te zera?