Matematické Fórum

Lordikcz · 14. 11. 2011 23:19

Ahoj chtěl bych se zeptat jak vypočítat všechny celočíselné dělitele -pokud možno co nejrychleji počítám,že asi jedinou možnost mám přes modulo protože se mi nepodařilo najít nic jiného :-/

FailED · 14. 11. 2011 23:55

Ahoj,
najdi prvočíselný rozklad, zbytek už je jednoduchý.

Lordikcz

Ahoj mám nalezený prvočíselný rozklad,ale co dál??

Můžu vynásobit prvočísla mezi sebou,ale to mi ještě nedá pořád všecky dělitele mohl byste mi poradit nějaký dobrý způsob jak získat všechny?

Jistě, můžu je roznásobit mezi sebou a pak roznásobovat ještě ty nové dělitele a přidávat jen ty u kterých platí,že číslo (n mod delitel)==0

n je to číslo pro které hledám dělitele ale to je pořád docela pomalé řekl bych.. :-(

FailED · 17. 11. 2011 13:33 — Editoval FailED (17. 11. 2011 13:34)

↑ Lordikcz:

Všechny dělitelé čísla $n=\prod_{i=1}^np_i^{k_i}$ jsou právě čísla $d=\pm\prod_{i=1}^np_i^{l_i}$ kde $p_i\in\mathbb{P},\,k_i, l_i\in\mathbb{N}, \,l_i\le k_i$ takže se znalostí prvočíselného rozkladu stačí vypsat všechna taková čísla.

mák · 17. 11. 2011 13:37

Příklad:
Zvolím číslo n=12600.
Rozložím jej a zjistím že je složený z těchto prvočísel:
$\left[ \left[ 2, 2, 2 \right], \left[ 3, 3 \right], \left[ 5, 5 \right], \left[ 7 \right] \right]$
Seznam čísel ale napíšu jako možné kombinace, které můžu z těchto čísel vytvořit:
$\left[ \left[ 1, 2, 4, 8 \right], \left[ 1, 3, 9 \right], \left[ 1, 5, 25 \right], \left[ 1, 7 \right] \right]$
Mám čtyři skupiny čísel jejichž členy můžu mezi sebou libovolně násobit (z každé skupiny pouze jedno číslo).
První dvě skupiny mezi sebou vynásobím a vzniklou skupinu napíši místo těchto dvou:
$\left[ \left[ 72, 24, 8, 36, 12, 4, 18, 6, 2, 9, 3, 1 \right], \left[ 1, 5, 25 \right], \left[ 1, 7 \right] \right]$
Ze čtyřech skupin mám již tři. Znovu vynásobím první dvě skupiny.
$\left[ \left[ 25,5,1,75, 15, 3, 225, 45, 9, 50, 10,2, 150, 30, 6, 450, 90, 18, 100, 20, 4, 300, 60, 12, 900, 180, 36, 200, 40, 8, 600, 120, 24, 1800, 360, 72 \right], \left[ 1, 7 \right] \right]$
Zůstaly mi už pouze dvě skupiny, které opět vynásobím mezi sebou. Pak je seřadím vzestupně, případně vyloučím duplicitní hodnoty (pokud se objeví). A je hotovo.

mák · 17. 11. 2011 13:41

V Maximě funkční kód:

Code:

Delitele(n):= block([z,i,j,S,T],
    S: maplist(lambda([z],makelist(z[1]^i,i,0,z[2])),ifactors(n)),
    while length(S)>1 do (print(S),
        T:[],
        Sa: S[1],
        Sb: S[2],
        for i:1 thru length(Sa) do (
            for j:1 thru length(Sb) do (
                T: cons(Sa[i]*Sb[j],T)
            )
        ),
        S: delete(Sa,S),
        S: delete(Sb,S),
        S: cons(sort(T),S)
    ),
    unique(sort(first(S)))
);

Lordikcz · 17. 11. 2011 13:54

↑ FailED:

Mohl byste mi ještě prosím rozvést ten vzoreček pro ty dělitele??

Nějak se u něj nemůžu těch dělitelů dopočítat asi nechápu dost dobře co je co :-(
pi -prvočíslo na i té pozici
li -snad mocnina na i-té pozici
n -počet prvočísel

a taky mi nejde do hlavy jak z toho dostanu ty dělitele když je tam ten znak pro součin řady z toho přece musí nakonec vypadnout +- to číslo ke kterému hledám ty dělitele ne?

jestli byste to mohl ukázat na příkladu možná by to pro mě bylo snadnější..
třeba dělitele pro číslo b=28=2*2*7

Mockrát Vám děkuji za pomoc :-)

Lordikcz · 17. 11. 2011 14:04

Už je to jasné z příspěvku od máka :-) Moc díky :-)

peter_2+2 · 24. 04. 2012 10:39

↑ mák:

Zajimavej postup.
Btw v tom cos napsal by se žádná čísla opakovat neměla(za předpokladu, že stejné číslo nejde rozdělit do dvou různých sad prvočísel, což nejde), dá se tak nakonci i spočítat, kolik těch dělitelů pro kontrolu bude.
4*3*3*2 respektive (3+1)*(2+1)*(2+1)*(1+1)... (*1+1 pro každé prvočíslo, které se neopakuje)

To +1 je samo pro variantu, že se v daném násobku to prvočíslo vyskytovat nebude vůbec, na tom tvým postupu je to myslím dost dobře vidět.

Akorád mezi nimi bude 1čka a pak samotné číslo od kterého se hledají dělitele, minimálně ta 1čka by se mezi ty dělitele počítat neměla.

Matematické Fórum

#1 14. 11. 2011 23:19

Vyhledání všech celočíselných dělitelů

#2 14. 11. 2011 23:55

Re: Vyhledání všech celočíselných dělitelů

#3 17. 11. 2011 12:01 — Editoval Lordikcz (17. 11. 2011 12:03)

Re: Vyhledání všech celočíselných dělitelů

#4 17. 11. 2011 13:33 — Editoval FailED (17. 11. 2011 13:34)

Re: Vyhledání všech celočíselných dělitelů

#5 17. 11. 2011 13:37

Re: Vyhledání všech celočíselných dělitelů

#6 17. 11. 2011 13:41

Re: Vyhledání všech celočíselných dělitelů

Code:

#7 17. 11. 2011 13:54

Re: Vyhledání všech celočíselných dělitelů

#8 17. 11. 2011 14:04

Re: Vyhledání všech celočíselných dělitelů

#9 24. 04. 2012 10:39

Re: Vyhledání všech celočíselných dělitelů

Zápatí