Matematické Fórum

jardasmid · 14. 04. 2009 22:31

Dobrý den,

mám nějaké číslo a potřebuji zjistit, jestli vzniklo vynásobením 2 prvočísel a když ano, tak kterých.

---
Nejprve jsem to chtěl udělat pomocí Eratosthenova síta: vyhledat prvočísla do číslo/2 a pak zkoušet násobky, ale to mi přijde strašně časově náročné. Nešlo by to udělat lépe?

Kondr · 15. 04. 2009 02:30

Stačí vyhledat prvočísla do $\sqrt{cislo}$ a každým z nich zkusit vydělit. Pokud je to úloha do programování, pak se mi toto řešení jeví jako adekvátní. Pokud jde o úlohu do teorie čísel, doporučil bych pomoci si např. Polardovým rho algoritmem: http://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm .

jardasmid · 15. 04. 2009 12:38

Díky. Stejně jsem to musel udělat do poloviny, protože potřebuju ověřit i to druhé číslo: např 56, sedí např. 2, vydělím, dostanu 28 a tu musím taky ověřit.

Kondr · 15. 04. 2009 13:14

↑ jardasmid:Ta prvočísla vážně stačí do $\sqrt{56}$ . Pro 56 najdu 2, vydělím, dostanu 28 a pak 28 zkusím dělit všemi nalezenými prvočísly do $\sqrt{28}$ . Doufám že je vidět, že to takto bude fungovat obecně.

jardasmid · 15. 04. 2009 14:15

↑ Kondr:To je pravda ... tak to zkusím upravit

Matematické Fórum

#1 14. 04. 2009 22:31

Násobek 2 prvočísel v C/C++

#2 15. 04. 2009 02:30

Re: Násobek 2 prvočísel v C/C++

#3 15. 04. 2009 12:38

Re: Násobek 2 prvočísel v C/C++

#4 15. 04. 2009 13:14

Re: Násobek 2 prvočísel v C/C++

#5 15. 04. 2009 14:15

Re: Násobek 2 prvočísel v C/C++

Zápatí