Matematické Fórum

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
!! 17.06.2018 (Jel.) Khanova škola zve nadšence ke spolupráci na překladech návodů pro učitele a rodiče.
! 04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17.01.2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17.01.2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
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

#1 22. 10. 2017 14:16

sio
Příspěvky: 41
Škola: Gymnazium Leonarda Stockela
Pozice: Študent
Reputace:   
 

Rozklad na prvočísla

Dobrý deň,

vedel by mi niekto poradiť efektívny algoritmus, ktorý vezme ako vstup číslo a ako výstup vráti počet možných rozkladov na súčin 2 čísel, kde ani jedno sa nesmie rovnať 1. Napr. 40 rozložíme na 2*20. To môžeme rozložiť na 2*2*10. To môžeme rozložiť na 2*2*2*5. Teda dokopy číslo môžme rozdeliť na súčin dvoch čísel 3 krát. Napr. číslo 7 ani raz.

Teda hľadáme algoritmus ktorý by robil toto:
numberOfFactorisations(40) = 3
numberOfFactoriastions(7)=0
.
.
.

Offline

 

#2 22. 10. 2017 16:21

mák
Místo: Vesmír, Galaxie MD
Příspěvky: 732
Reputace:   57 
 

Re: Rozklad na prvočísla

Zdravím,
pokud jsem pochopil co říkáš, tak chceš sečíst počet celočíselných výsledků podílu zkoušeného čísla od 2 do jeho druhé odmocniny.


ale jestli je efektivní to nevím...

Offline

 

#3 23. 10. 2017 08:48

mracek
Zablokovaný
Příspěvky: 164
Reputace:   
 

Re: Rozklad na prvočísla

Rozklad na prvocisl = algoritmus, ktery se pokusi cislo delit celociselne prvocisly od 2 po zbytek po deleni. Nebo si to muzes zjednodusit a delit ho nejdrive 2, dokud to jde a pak lichymi cisly.

40 / 2 = 20
20 / 2 = 10
10 / 2 = 5
5 / prvocislem 3-(n-1) (5) NEBO lichymi cisly mezi 3-n
5 / 3 = 1 zbytek 2 NE
Dalsi prvocislo <n neni, takze 5 je delitelne uz jen samo sebou
2 * 2 * 2 * 5

A nebo jsou rychlejsi algoritmy zalozene na matematice, kdy se da postupovat od nejvetsiho prvocisla.

Offline

 

#4 23. 10. 2017 20:50 — Editoval misaH (23. 10. 2017 20:56)

misaH
Příspěvky: 9643
 

Re: Rozklad na prvočísla

↑ sio:

Ahoj.

Teda dokopy číslo môžme rozdeliť na súčin dvoch čísel 3 krát.

To čo uvádzaš ale nie je vždy súčin    d v o c h    čísel...

To by asi potom malo byť 

$40=2\cdot20=4\cdot10=5\cdot8$

Ale možno si to tak myslel...

Nesúvisí to nejako s počtom deliteľov?

Ja žiakov učím hľadať všetky delitele rozkladom na súčin dvoch čísel...

Offline

 

#5 23. 10. 2017 20:51 — Editoval misaH (23. 10. 2017 20:57)

misaH
Příspěvky: 9643
 

Re: Rozklad na prvočísla

↑ mracek:

Prosím ťa, prečítal si si zadanie?

Autor chce niečo úplne iné než čo píšeš ty.

To naozaj nedokážeš pochopiť text?

Offline

 

#6 24. 10. 2017 16:47

check_drummer
Příspěvky: 2554
Reputace:   66 
 

Re: Rozklad na prvočísla

↑ sio:
Ahoj, nejedná se o kombinatorickou úlohu? Mějme ki prvků ai a chceme určit kolik neprázdných "podmnožin" z těchto všech prvků a1,a2,.. (prvky ai se mohou opakovat, proto píšu "podmnožina" v uvozovkách) lze sestrojit, přičemž prvky ai považujeme za nerozlišitelné. Tedy např. pro k1=2, k2=2 jde o "podmnožiny" a1; a2; a1,a1; a2,a2; a1,a2; a1,a1,a2; a1,a2,a2; a1,a1,a2,a2.

A u toho problému s prvočísly jde dle mého o to, že pro zkoumané číslo n chápeme n jako součin čísel $a_i^{k_i}$, kde ai jsou prvočísla v rozkladu n. (S tím, že dle podmínek úlohy nebudeme uvažovat tu podmnožinu, která tvořena všemi ai).


Nikdy nechibuji.

Offline

 

#7 24. 10. 2017 17:43 — Editoval vanok (24. 10. 2017 17:57)

vanok
Příspěvky: 12821
Reputace:   714 
 

Re: Rozklad na prvočísla

Ahoj ↑ check_drummer:,
Ja to rozumiem takto
Dane cislo sa postupne pise ako sucin dvoch faktorov
2.20
4.10
5.8
8.5
10.4
20.2
Akoze na poradi nazalezi,tak staci uvazovat 3 prve rozkady.
To da myslienku algoritmu
Staci urcit pocet delitelov daneho cisla mensich ako jeho druha odmocnina  ( dualne mame tolko isto delitelov vadcich ako jeho druha odmocnina).
Ina myslienka je urcit pocet delitelov D cisla inych ako 1 a dane cislo. 
Potom pocet faktorizacii na 2 casti sa lahko urci  ...

Poznamka.  ( umyselne tu ide o spécialnu situaciu)
Ak sa niekto trochu bavil z delitelmi cisiel ako napr  v tomto specialnom pripade $p_1^a.p_2^b.p_3^c$ tak iste vie, pocet jeho vsetkych delitelov je $(a+1)(b+1)(c+1)$ kde $p_i$ su rozne prvocisla.


Srdecne Vanok
The respect, the politeness are essential qualities...and also the willingness.
Do not judge the other one.
Ak odpovedam na nejaku otazku. MOJ PRINCIP NIE JE DAT ODPOVED ALE UKAZAT AKO SA K ODPOVEDI DOSTAT

Offline

 

#8 25. 10. 2017 22:05

check_drummer
Příspěvky: 2554
Reputace:   66 
 

Re: Rozklad na prvočísla

↑ vanok:
Ahoj, já jsem se pokoušel namísto algoritmu hledat explicitní vzorec na vyjádření počtu těch rozkladů. No ale i tak je to v obecnosti časově náročná úloha, protože nalézt prvočíselné činitele daného čísla je obecně (časově) složitý problém.


Nikdy nechibuji.

Offline

 

#9 26. 10. 2017 08:37 — Editoval vanok (26. 10. 2017 08:39)

vanok
Příspěvky: 12821
Reputace:   714 
 

Re: Rozklad na prvočísla

↑ check_drummer:,
Pozdravujem,
To mas pravdu, riesenie je jednoduche pokial je znamy prvociselny rozlad daneho cisla ( co som predpokladal). Inac je to ( pre nahoodne dane cislo velmi,velmi) tazko riesitelny problem.


Srdecne Vanok
The respect, the politeness are essential qualities...and also the willingness.
Do not judge the other one.
Ak odpovedam na nejaku otazku. MOJ PRINCIP NIE JE DAT ODPOVED ALE UKAZAT AKO SA K ODPOVEDI DOSTAT

Offline

 

#10 26. 10. 2017 08:59

Honzc
Příspěvky: 3797
Reputace:   210 
 

Re: Rozklad na prvočísla

↑ sio:
Pro zjištění počtu možných rozkladů čísla N na součin 2 čísel je opravdu nejprve nutné udělat rozklad takového čísla na součin prvočísel.
Pak zjistíš počet dělitelů takového čísla - viz.↑ vanok: (zdravím).
Protože počet dělitelů p obsahuje i čísla 1 a N je  pro zjištění počtu součinů 2 čísel pak už jenom:
a) je-li počet dělitelů p sudé číslo:  p/2-1
b) je-li počet dělitelů p liché číslo:  (p-1)/2  - zkus popřemýšlet jaké je  číslo N, když má lichý počet dělitelů

Offline

 

#11 06. 02. 2018 01:58

MichalAld
Příspěvky: 939
Reputace:   26 
 

Re: Rozklad na prvočísla

Pokud na ten algoritmus někdo přijdete, tak se nestyďte to sem napsat, šel by totiž použít k prolomení té RSA šifry.

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson