Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
Dobrý den,
je nějakým způsobem možné zjistit počet dělitelů čísla, aniž bych předtím zjistila, jací ti dělitelé konkrétně jsou?
A případně jak zjistit všechny dělitele čísla, např. 441 či 819? Hledala jsem nějaký kloudný způsob na internetu, ale všechny, které jsem našla, mi fungují jen pro menší cifry.
Offline
↑ luciesuch:
Podle mě musíš udělat prvočíselný rozklad. Z rozkladu pak kombinatoricky zjistíš počet dělitelů.
Offline
↑ luciesuch:
Rozložíš dané číslo na součin prvočísel
Tedy
[mathjax]n=p_{1}^{\alpha _{1}}\cdot p_{2}^{\alpha _{2}}\cdot... p_{m}^{\alpha _{m}}[/mathjax]
Pak počet dělitelů čísla n (včetně 1 a n) je roven
[mathjax]p=(\alpha _{1}+1)(\alpha _{2}+1)...(\alpha _{m}+1)[/mathjax]
Např. pro čísla co uvádíš
441=3^2*7^2 a tedy p= 3*3=9 (včetně čísel 1 a 441) Pozn. chceš-li vyloučit 1 a 441 stačí od 9 odečíst 2
(3,7,9,21,49,63,147)
819=3^2*7*13 p=3*2*2=12 (12-2=10)
(3,7,9,13,21,39,63,91,117,273)
Offline
Já myslím, že žádné velké zázraky ohledně dělitelnosti se vymyslet nedají, protože obtížnost nalezení rozkladu se využívá i při šifrování.
Jediné co vím, že se dá, se dá určit, jestli je číslo prvočíslem nebo není - aniž bychom ten rozklad museli nalézt. Ale metoda není úplně 100% spolehlivá, je tam nějaká malá možnost, že to určíme chybně.
Ale u čísel do 1000 není až takový problém všechny dělitele nalézt, protože stačí prověřit čísla od 2 do odmocniny z 1000, což je něco přes 30.
Navíc ty čísla co zmiňuješ jsou dělitelné 3, takže jeden dělitel už máš, a ten zbytek už bude 3x menší, takže už hledáš jen čísla do odmocniny z 300, což je nějakých 17. Ona jsou dokonce na první pohled dělitelná devíti, a když je podělíš 9, tak to co zbývá už je menší než 100, a tam už pak stačí zkoušet čísla menší než 10. A to reálně znamená jen sedmičku, protože u 2, 3, 5 se to dá poznat na první pohled.
Takže třeba 819:9 je 91, to není dělitelné ani 2, ani 3, ani 5, takže stačí vyzkoušet sedmičku, a vyjde že je to 7*13. A máš to.
Offline
↑ MichalAld:
Mám dojem, že jsi špatně četl zadání. Zadavatelka nepotřebuje udělat prvočíselný rozklad, ale zjistit počet dělitelů nějakého čísla.
(ikdyž pro jeho určení, ten rozklad potřebuje také)
Offline
↑ Honzc: To je právě můj problém, pro určení počtu dělitelů jsem v testu použila prvočíselný rozklad, a profesorem mi bylo řečeno, že jsem to udělala zbytečně navíc - úkolem totiž bylo pouze určit počet dělitelů čísla. Logicky mi ale připadá, že počet dělitelů přeci nemohu určit, aniž bych dělitele znala. Studuji dálkově a pan profesor na maily s dotazy neodpovídá, tudíž pořádně ani nemám čeho se chytit.
Offline
↑ luciesuch:
Až ti pan profesor odpoví, tak to sem napiš, mě by totiž také zajímalo, jak určit ten počet, bez prvočíselného rozkladu.
Ono možná půjde o to vysvětlit co znamená věta "....aniž bych dělitele znala."
Při způsobu, který jsem ti popsal totiž všechny dělitele znát nepotřebuješ. (viz. [mathjax]p=(\alpha _{1}+1)(\alpha _{2}+1).....[/mathjax])
Offline
↑ luciesuch:
Ahoj,
prvočíselný rozklad ještě neznamená znalost všech dělitelů. Znáš jenom ty prvočíselné. Další znát nemusíš. Jejich počet zjistíš kombinatoricky z toho rozkladu.
Jestliže vím, že
12 = 2^2*3,
taky vím, že dělitelé jsou 1; 12 (ti jsou samoozřejmí), dále 2; 3 plus ještě další, jejichž hodnotu ale už nemusím znát.
Ten rozklad ale podle mě znát musíš (ani mě nenapadá, jak by to šlo bez něj).
Offline
↑ Eratosthenes:
Ahoj, jak píše Honzc, stačí znát jen ty exponenty, ale otázka je, zda je lze zjistit aniž bych zjistil ta prvočísla. :-)
Offline
↑ check_drummer:
No právě o to jde. Prvočinitele bez exponentů zjistíš, ale obráceně :-(
Offline
Pozdravujem ↑ laszky:,
Najprv prajem stastlivy Novy rok.
Mas pravdu.
Presnejsie mame :
https://en.wikipedia.org/wiki/Divisor_function .
A aj toto je uzitocne pozriet
https://oeis.org/A000005 .
Offline
Pozdravujem ↑ luciesuch:,
Este jedna metoda, ( no asi trochu unavna).
Ukazem jej princip na cisle 441.
Urcime najprv [mathjax]\sqrt { 441}[/mathjax] a konstatujeme ze je to 21.
Potom postupne delme 441 cislami
1 , 2, 3,…,21.
A tak vidime, ze 1 deli 441 a tak 441=1.441 ( co da dva delitele 1 a 441)
A tiez vidime, ze 2 nedelu 441.
Potom 3 deli 441 a tak….
….
Na koniec mame 441= 21.21 (co da jedneho delitela 21).
A tak si takto urcila vsetki delitele.
No aj tu je mozne prakticky pouzit tuto metodu len pre dost male cisla… no ale urcite uz aj na ZS.
Offline