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
❗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
#1 29. 11. 2014 14:42
dělitelnost prvočísel
Dobré odpoledne,
potřebovala bych poradit s tím to příkladem: Co nejúspornějším způsobem rozhodněte, která z daných čísel jsou prvočísla:
a) 667 b)677 c)439 d)1591 e)4187
Jakým nejúspornějším způsobem byste to řešili vy?
Děkuji
Offline
#2 29. 11. 2014 17:27
#3 03. 12. 2014 12:11
Re: dělitelnost prvočísel
↑ check_drummer:
Prave bych si to vypsala..všechny ty delitele, ale ma to byt co nejúsporněji. Prosim poradte :)
Offline
#4 03. 12. 2014 21:53
- check_drummer
- Příspěvky: 5506
- Reputace: 106
Re: dělitelnost prvočísel
↑ Samii:
Stačí když najdeš alespoň jednoho (netriviálního) dělitele a už víš, že to není prvočíslo.
"Máte úhel beta." "No to nemám."
Offline
#5 04. 12. 2014 07:00
Re: dělitelnost prvočísel
↑ Samii:
Nejdříve je třeba si uvědomit, že rozklad nějakého čísla se skládá z prvočísel. Tedy číslo jehož rozklad chceme udělat stačí dělit prvočísly od 2 do prvočísla, které je menší než druhá odmocnina z daného čísla.
Tedy pro
439 stačí zkoušet dělitelnost pro prvočísla do 19
667 do 23
677 do 23
1591 do 37
4187 do 61
Dále je zřejmé, že dvojkou není dělitelná žádné (všechny jsou lichá)
Také 3-mi a 5-ti není dělitelné žádné z nich-stačí využít pravidel pro dělitelnost 3-mi a 5-ti.
Pro nejúspornější postup bych zkusil dělit dané číslo postupně prvočísly od největšího možného postupně do nejmenšího
Ukázka pro 439
439:19 ne, 439:17 ne, 439:13 ne, 439:11 ne, 439:7 ne - tedy 439 je prvočíslo
pro 667
667:23=29 - 667 není prvočíslo (667=23*29)
pro 677 stačí začít 19 - vyjde prvočíslo
pro 1591
1591:37=43 - 1591 není prvočíslo (1591=37*43)
pro 4187
4187:61 ne, 4187:59 ne, 4187:53=79 - 4187 není prvočíslo (4187=53*79)
Offline
#6 05. 12. 2014 10:42
- Eratosthenes
- Příspěvky: 3111
- Reputace: 140
Re: dělitelnost prvočísel
ahoj ↑ Samii:,
jde o to, co znamená "nejúspornější způsob". Já bych za sebe nechal rozhodnout tuto funkci:
Function Prvocislo(n:Integer):Boolean;
var Delitel :LongInt;
NalezenDelitel:Boolean;
begin
NalezenDelitel:=False;
Delitel:=2;
Repeat
if (n/Delitel)=Trunc(n/Delitel) then NalezenDelitel:=True;
inc(Delitel);
Until (Delitel>sqrt(n)) or NalezenDelitel;
Prvocislo:=not NalezenDelitel;
end;
Počítač by se, pravda, trochu nadřel, ale já bych určitě uspořil:)
Budoucnost patří aluminiu.
Offline
#7 06. 12. 2014 12:03
- check_drummer
- Příspěvky: 5506
- Reputace: 106
Re: dělitelnost prvočísel
↑ Eratosthenes:
Nebo ještě lépe - nechat úlohu (jakkoliv) vyřešit někoho jiného. :-)
"Máte úhel beta." "No to nemám."
Offline