| Autor | Zpráva | ||
|---|---|---|---|
| Koprda Profil * |
#1 · Zasláno: 17. 3. 2015, 16:36:06
Dobrý den,
chtěl bych se zeptat jestli někdo nezná nějaký jednoduchý program v JS na výpis prvočísel, např. do 100 ? |
||
| lionel messi Profil |
#2 · Zasláno: 17. 3. 2015, 16:44:26
Koprda:
Zdravím, trošku som hľadal a dostal sa k tomuto: stackoverflow.com/questions/11966520/how-to-find-prime-numbers-between-0-100. Verím, že s angličtinou si dokážete poradiť, podstatná časť je v prvej odpovedi. Uvedená funkcia by mala používať Eratostenovo sito. |
||
| Koprda Profil * |
#3 · Zasláno: 17. 3. 2015, 16:53:24
Díky za tip. Je to na mě trochu složité. Máme první hodinu JS a hned máme takovýto příklad.
|
||
| lionel messi Profil |
#4 · Zasláno: 17. 3. 2015, 16:58:54
Koprda:
„Je to na mě trochu složité.“ To verím. Ešte som sa na to trochu pozrel, jednoduchšie na pochopenie by malo byť toto riešenie: stackoverflow.com/questions/17389350/prime-numbers-javascript, len si ho zrejme budeš musieť máličko upraviť. Kód som netestoval, ale pochádza od skúseného užívateľa. |
||
| Joker Profil |
#5 · Zasláno: 17. 3. 2015, 17:19:22
Koprda:
function prvocislaDo100() {
return [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];
}:-) Jinak možná intuitivnější způsob, než ten v [#2], je zkoumání dělitelnosti. Základ je pro všechna čísla v cyklu volat kontrolu, jestli je prvočíslo. Ta kontrola bude jednoduše zkoumat, jestli číslo je dělitelné nějakým jiným číslem. Nejdřív zkusí, jestli je dělitelné dvojkou, a postupně bude pokračovat. Kam až? Tak pokud číslo má dva stejně velké dělitele, jsou ti dělitelé jeho druhá odmocnina (např. 16 = 4*4 a tedy sqrt(16) = 4). Pokud má dva různé dělitele, musí být jeden nižší, než druhá odmocnina toho čísla, a druhý vyšší (jinak by logicky nemohlo vyjít to původní číslo). Čili stačí projít jen čísla do druhé odmocniny kontrolovaného čísla. |
||
| Juraj Hajdúch Profil |
#6 · Zasláno: 17. 3. 2015, 17:35:21
Heh, tak som si trochu zatestoval :o) na SW: W7 Ultimate SP1, PHP ako modul Apache; HW: Pentium dual core 2,8 GHz, 3 GB RAM
// fce skopírovaná z netu, stackoverflow.com
function sieveOfEratosthenes($top){
$number = (int) 2;
$range = (array) range(2, $top);
$primes = (array) array_combine($range, $range);
while($number * $number < $top){
for($i = $number; $i <= $top; $i += $number){
if($i == $number){
continue;
}
unset($primes[$i]);
}
$number = next($primes);
}
return $primes;
}
for($i = 10; $i <= 1000000; $i *= 10){
$time_start = microtime(true);
echo "Do cisla ".$i." je ".count(sieveOfEratosthenes($i))." prvocisel.<br />";
$time = microtime(true) - $time_start;
echo "Vypocet trval ".$time." sekund.<br /><br />";
}a výsledky Do cisla 10 je 4 prvocisel. Vypocet trval 0 sekund. Do cisla 100 je 25 prvocisel. Vypocet trval 0 sekund. Do cisla 1000 je 168 prvocisel. Vypocet trval 0.00099992752075195 sekund. Do cisla 10000 je 1229 prvocisel. Vypocet trval 0.012001037597656 sekund. Do cisla 100000 je 9592 prvocisel. Vypocet trval 0.17000889778137 sekund. u poslednej iterácie (1M) mi vypísalo fatálnu chybu 'Allowed memory size of ...' Dosti rychlý algoritmus |
||
| 1Pupik1989 Profil |
Nemá smysl testovat každé číslo.
1. Pokud je číslo menší nebo rovno 3 a větší než 1, pak je prvočíslo. 2. Pokud je prvočíslo dělitelné 2 nebo 3 beze zbytku, pak není prvočíslo. To můžeme i v cyklu vynechat. 3. Testování čísla 4 můžeme vynechat. Protože už jsme testovali 2. Čili když to vezmeme kolem a kolem: function isPrime(n) {
if(n <= 3){ return n>1; }
if(n%2 == 0 || n%3 == 0){ return false; }
var sqrtN = Math.floor(Math.sqrt(n));
for(var i = 5; i <= sqrtN; i += 6) {
if(n%i == 0 || n%(i+2) == 0){ return false; }
}
return true;
};Vycházel jsem z wikipedie a zdrojového kódu pro Javu. |
||
| Juraj Hajdúch Profil |
Díky 1Pupik1989
Tedy var finish = 100;
for(i = 1; i <= finish; i++){
if(isPrime(i)){
// je prvocislo, vypsat
}
else{
// neni prvocislo, ignorovat
}
} |
||
| Keeehi Profil |
#9 · Zasláno: 17. 3. 2015, 18:08:44
Juraj Hajdúch:
Eratostenovo síto je velmi rychlý algoritmus. Měl by být rychlejší než postupné testování s isPrime. Nicméně má lineární nároky na paměť oproti konstantní paměti druhého algoritmu. Ta paměť se dá optimalizovat, ovšem vždy je to jen o konstantu. Pokud by se použilo bitové pole tak oproti poli integerů (předpokládejme 4 bajty) bude naše pole 32x menší. Což je určitě lepší ovšem lépe to nepůje. Za rychlost se prostě platí pamětí. Ale to tak bývá u většiny algoritmů. |
||
| 1Pupik1989 Profil |
#10 · Zasláno: 17. 3. 2015, 18:41:53
function primesToLimit($top){
$range = [];
for($n=2;$n<$top;$n++){
if($n <= 3 && $n>1){
$range[] = $n;
}else if($n%2 == 0 || $n%3 == 0){
continue;
}else{
$add = true;
for($i = 5; $i*$i <= $n; $i += 6) {
if($n%$i === 0 || $n%($i+2) === 0){
$add = false;
break;
}
}
if($add){
$range[] = $n;
}
}
}
return $range;
}
for($i = 10; $i <= 100000; $i *= 10){
$time_start = microtime(true);
echo "Do cisla ".$i." je ".count(primesToLimit($i))." prvocisel.<br />";
$time = microtime(true) - $time_start;
echo "Vypocet trval ".$time." sekund.<br /><br />";
} Do cisla 10 je 4 prvocisel. Vypocet trval 0 sekund. Do cisla 100 je 25 prvocisel. Vypocet trval 0 sekund. Do cisla 1000 je 168 prvocisel. Vypocet trval 0 sekund. Do cisla 10000 je 1229 prvocisel. Vypocet trval 0.0060009956359863 sekund. Do cisla 100000 je 9592 prvocisel. Vypocet trval 0.10500597953796 sekund. Ten od Juraj Hajdúch má u mě: Do cisla 10 je 4 prvocisel. Vypocet trval 0 sekund. Do cisla 100 je 25 prvocisel. Vypocet trval 0 sekund. Do cisla 1000 je 168 prvocisel. Vypocet trval 0.003000020980835 sekund. Do cisla 10000 je 1229 prvocisel. Vypocet trval 0.02800178527832 sekund. Do cisla 100000 je 9592 prvocisel. Vypocet trval 0.10000514984131 sekund. Takže bych to jako nějaké drama neviděl. Plus můj není tolik náročný na paměť, takže 1M zvládne. Do cisla 1000000 je 78498 prvocisel. Vypocet trval 2.1441221237183 sekund. |
||
| Juraj Hajdúch Profil |
#11 · Zasláno: 17. 3. 2015, 18:53:46
1Pupik1989:
Výborne, predbehol si ma :D. Áno, tie hodnoty sú pomerne podobné, takže je v praxi zbytočné sa tým zaťažovať (ak teda nechce niekto počítať do bambilión), na PC mi to zvládlo už 10M, 17,4 sekund. Považujem túto tému pre mňa za vyriešenú :). Ďakujem. |
||
| Keeehi Profil |
1Pupik1989:
Dvojnásobného zrychlení se dá dosánout když proměnnou n budeš incermentovat po 2 v lichých číslech. |
||
| 1Pupik1989 Profil |
Keeehi:
Ano, všechna sudá bych mohl vynechat, to je pravda. S tím už si pohraje autor tématu určitě. //edit: Tak finální kód, bych viděl zhruba následovně: function primesToLimit($top){
if($top === 2){ return Array(2); }
if($top === 3){ return Array(2,3); }
$range = Array(2,3);
for($n=5;$n<=$top;$n+=2){
if($n%3 == 0){
continue 1;
}else{
for($i = 5; $i*$i <= $n; $i += 6) {
if($n%$i === 0 || $n%($i+2) === 0){
continue 2;
}
}
$range[] = $n;
}
}
return $range;
}Nebo případně místo $i*$i použít odmocninu $n. Na rychlosti už to znát ale není.
|
||
| _es Profil |
#14 · Zasláno: 17. 3. 2015, 21:01:11
Keeehi:
„proměnnou n budeš incermentovat po 2 v lichých číslech.“ Alebo tam začlení aj 3, 5 (7, 11, 13, ...)... Spôsobov zrýchlenia je veľa. |
||
| mimochodec Profil |
#15 · Zasláno: 17. 3. 2015, 21:26:21
_es:
„Alebo tam začlení aj 3, 5 (7, 11, 13, ...)“ Už do cyklu? Jak? |
||
| Keeehi Profil |
#16 · Zasláno: 17. 3. 2015, 22:56:32
mimochodec:
Není to tak jednoduché jako vždy přičítat 2 ale dá se. Pro 2 a 3 musíš střídat přičítání +4, +2, +4, +2, +4, +2, ... Pro 2, 3 a 5 to je +6, +4, +2, +4, +2, +4, +6, +2, +6, +4, +2, +4, +2, +4, +6, +2, ... |
||
| Tomáš123 Profil |
#17 · Zasláno: 17. 3. 2015, 23:00:16
Keeehi:
Iba zo zaujímavosti... Ako si prišiel na takýto algoritmus? Vôbec v tom nevidím súvislosť. |
||
| juriad Profil |
#18 · Zasláno: 17. 3. 2015, 23:02:58
Tomáš123:
Každé 2*3-té číslo je dělitelné 6. Každé 2*3*5-té číslo je dělitelné 30. Teď si jen napíšeš, která z čísel 1-6 (1-30) jsou zajímavá pro test prvočíselnosti. A vypočítáš rozdíly mezi dvěma po sobě jdoucími. |
||
| Tomáš123 Profil |
juriad:
„A vypočítáš rozdíly mezi dvěma po sobě jdoucími.“ Prečo? Sú medzi prvočíslami pravidelné rozostupy? |
||
| juriad Profil |
Tomáš123:
„Sú medzi prvočíslami pravidelné rozostupy?“ To nikdo neví. :-) Ale tady se bavíme o tom, že není třeba zkoušet všechna čísla, ale jen ty perspektivní - první krok byl vyloučit sudá čísla (násobky dvou). Další krok je vyloučit násobky dvou a tří. A jak si můžeš všimnout, zbytky po dělení dvěma a třemi se začnou po šesti číslech opakovat. Podobně to funguje u vyloučení násobků 2, 3 a 5. Tam se začnou zbytky po dělení těmi čísly opakovat až po 30. Při vyloučení 2 a 3 stačí testovat jen 2 čísla z 6. Při vyloučení 2, 3 a 5 stačí testovat jen 8 ze 30. (Spočítej ty tučné v [#16].) Tím opakováním myslím: 1 % (2, 3) = (1, 1) 2 % (2, 3) = (0, 2) 3 % (2, 3) = (1, 0) 4 % (2, 3) = (0, 1) 5 % (2, 3) = (1, 2) 6 % (2, 3) = (0, 0) 7 % (2, 3) = (1, 1) 8 % (2, 3) = (0, 2) 9 % (2, 3) = (1, 0) 10 % (2, 3) = (0, 1) 11 % (2, 3) = (1, 2) 12 % (2, 3) = (0, 0) Vidíš to pravidlo? |
||
| Keeehi Profil |
Tomáš123:
„Prečo? Sú medzi prvočíslami pravidelné rozostupy?“ Kdyby byly, tak ověřování prvočíselnosti by byla brnkačka. Ovšem mezi neprvočísly jsou "pravidelné" rozestupy. Když otestujeme nějaké číslo, tak můžeme určit že dalších x určitě prvočíslem není a proto je ani nemusíme testovat. en.wikipedia.org/wiki/Wheel_factorization Je to krásně vidět na tom obrázku. My víme, že v těch žlutých oblastech určitě žádná prvočísla najsou a tak nám stačí testovat jenty nežluté, kde si nejsme jisti. Ale třeba někdo jednou přijde na nějaký algoritmus, který dokáže vzít prvočíslo a určit o kolik čísel dál je další. |
||
| juriad Profil |
Keeehi:
Zatím se ví, že v rozsahu n a 2n je alespoň jedno prvočíslo. Dále se ví, že podíl počtu prvočísel vůči všem číslům v rozsahu 1 až n je přibližně n/ln n. |
||
| Joker Profil |
Tomáš123:
„Prečo? Sú medzi prvočíslami pravidelné rozostupy?“ Ne, ale mezi čísly dělitelnými určitým číslem jsou pravidelné rozestupy :-) Vybraná čísla nejsou ještě prvočísla, ale čísla nedělitelná žádným z těch čísel. A ty mezi sebou pravidelné rozestupy mají (resp. jejich rozestupy se pravidelně opakují). juriad: > „Sú medzi prvočíslami pravidelné rozostupy?“ > To nikdo neví. :-) Já bych si dovolil tvrdit, že ví :-) Prvočísla nemají pravidelné rozestupy, čím dál od nuly, tím větší rozestupy mezi prvočísly. edit: Případně důkaz: Existuje jediná dvojice prvočísel (2 a 3) s rozestupem 1. Kdyby se rozestupy v nějakém cyklu opakovaly, muselo by dvojic s rozestupem 1 být nekonečně mnoho. |
||
| juriad Profil |
Joker:
Pokud se pravidelnými rozestupy myslí aritmetická posloupnost, pak samozřejmě nic takového neplatí. Za pravidelný rozestup jsem považoval rozestup, který je řízen pravidlem. A to může být jakkoli složité, pokud jeho Kolmogorovská* složitost nebude nekonečná (prvočísel je nekonečně mnoho, tedy vylučuji případ, že samotný seznam je nejlepší možnou reprezentací). * Co to, takový užitečný pojem a ono k tomu snad neexistuje nic v češtině. |
||
| Tomáš123 Profil |
#25 · Zasláno: 17. 3. 2015, 23:39:45
tí, čo regovali:
Nerozumiem úplne všetkému (sčasti kvôli únave). Vy všetci už máte vysoké školy a preberali ste to. Ja som sa tam ešte nedostal, ale zaujímajú ma takéto teórie, takže ďakujem, že mi to vysvetľujete. Keeehi: Fakt dobrý obrázok. juriad: „Zatím se ví, že v rozsahu n a 2n je alespoň jedno prvočíslo.“ Ak je n párne, tak ani jedno nie je prvočíslo. Ak teda ďalšia veta nenadväzuje potenciálnou spojkou a súčasne (lebo práve tomu zápisu n/ln n nerozumiem). Joker: Čo môžme vedieť... Možno existuje nejaká spojitosť. Možno je nejaký koeficient, ktorým treba vynásobiť nejaký zložitý výraz zložený z prvočísel. :-) |
||
| juriad Profil |
Tomáš123:
V rozsahu znamená, mezi čísly n, n+1, n+2, ..., 2n-1, 2n. Například mezi čísly 5 - 10 je prvočíslo 7. Mezi 8 - 16 je prvočíslo 11 a 13. Mezi 25 a 50 jsou to 29, 31, 37, 41, 43, 47. Ta druhá věta povídá o tom, kolik je prvočísel menších než nějaké číslo (vše statisticky, nikoli přesně): cs.wikipedia.org/wiki/Prvo%C4%8D%C3%ADseln%C3%A1_v%C4%9Bta Všimni si, že „Jinými slovy můžeme říct, že průměrná mezera mezi dvěma prvočísly blízko N je zhruba ln(N).“ je hodně daleko od mezery v Bertrandově postulátu, která ve velká až N. Zajímavé články na úrovni střední školy v češtině má PRAžský SEminář. |
||
| Tomáš123 Profil |
juriad:
Už viem čomu nerozumiem. Na základe vety: „Při vyloučení 2 a 3 stačí testovat jen 2 čísla z 6“ mi došlo o čo v Keeehiho zápise ide (i keď aj bez nej som bol schopný určiť, že ide o vylúčenie kombinácii násobkov násobkov niektorých čísel). Ďakujem za hlbšie vysvetlenie. Stále mi však nie je jasné, prečo práve: „+6, +4, +2, +4, +2, +4, +6, +2“ Áno, súčet je 30. Ale prečo práve takéto poradie? Ide o to, že ak si zoberieme ľubovoľné číslo tak musíme kontrolovať každé n + 6, n + 4, n + 2, n + 4, n + 2, n + 4, n + 6 a n + 2 číslo? Prepáč, ale stále mi to nie je jasné. Na dnes to zabalím, lebo o pár minút mi nebude jasné, ani prečo je 1+2 práve 3. Čo sa týka prvočíselnej vety, rozumiem podstate, vzorec mi uniká, ale logaritmy sme ešte nebrali, takže to teraz nie je podstatné. |
||
| Keeehi Profil |
#28 · Zasláno: 18. 3. 2015, 00:29:20
Tomáš123:
„Ale prečo práve takéto poradie?“ Protože zrovna tak to vychází. Já tu sekvenci doteď nezal, ale jednoduše jsem ji vypočítal 2: 1X-X-X-X-X-X-X-X-X-X-X-X-X-X-X 3: 1-X--X--X--X--X--X--X--X--X--X 5: 1---X----X----X----X----X----X --------------------------------- r: -XXXXX-XXX-X-XXX-X-XXX-XXXXX-X Vytvořím si tři řady. Tam kde je X to nemusím testovat protože vím že tam prvočíslo není (Protože to konstuuji pro prvočísla 2,3,5 tak je nemusím testovat, jelikož už je znám), a tam kde je pomlčka, tam by teoreticky být mohlo. Pro výpočet řádku r prostě v každém sloupci zkontroluji, zda tam je alespoň jedno X, pokud ano tak si ho napíšu i do svého řádku r protože vím, že to testovat nemusím. No a výsledná sekvence 6424242 je jasně viditelná. Taky je z toho vidět, že největší úsporu přináší menší čísla. Taky je to krásně vidět en.wikipedia.org/wiki/Sieve_of_Eratosthenes kde jsou porovnány jednotlivé možnosti. |
||
| Tomáš123 Profil |
#29 · Zasláno: 18. 3. 2015, 00:36:49
Keeehi:
Našiel si spôsob, ako mi to vysvetliť. Ďakujem. O Eratostenovom site som vedel, len som si to nebol schopný dať dohromady. |
||
| mimochodec Profil |
#30 · Zasláno: 18. 3. 2015, 08:55:52
Keeehi:
„Není to tak jednoduché jako vždy přičítat 2 ale dá se. Pro 2 a 3 musíš střídat přičítání“ Jasně. Mně šlo o to, že tou dobou ještě byla řeč o cyklu. Teď už se diskuse posunula trochu dál :) Ještě jedna zajímavost k prvočíslům. Jestli neznáte Ulamovu spirálu... http://en.wikipedia.org/wiki/Ulam_spiral |
||
|
Téma pokračuje na další straně.
|
|||
0