abclinuxu.cz AbcLinuxu.cz itbiz.cz ITBiz.cz HDmag.cz HDmag.cz abcprace.cz AbcPráce.cz
AbcLinuxu hledá autory!
Inzerujte na AbcPráce.cz od 950 Kč
Rozšířené hledání
×
    včera 19:55 | IT novinky

    Americký výrobce čipů Intel propustí 15 procent zaměstnanců (en), do konce roku by jich v podniku mělo pracovat zhruba 75.000. Firma se potýká s výrobními problémy a opouští také miliardový plán na výstavbu továrny v Německu a Polsku.

    Ladislav Hagara | Komentářů: 6
    včera 17:33 | Komunita

    MDN (Wikipedie), dnes MDN Web Docs, původně Mozilla Developer Network, slaví 20 let. V říjnu 2004 byl ukončen provoz serveru Netscape DevEdge, který byl hlavním zdrojem dokumentace k webovým prohlížečům Netscape a k webovým technologiím obecně. Mozille se po jednáních s AOL povedlo dokumenty z Netscape DevEdge zachránit a 23. července 2005 byl spuštěn MDC (Mozilla Developer Center). Ten byl v roce 2010 přejmenován na MDN.

    Ladislav Hagara | Komentářů: 0
    včera 14:55 | Nová verze

    Wayback byl vydán ve verzi 0.1. Wayback je "tak akorát Waylandu, aby fungoval Xwayland". Jedná se o kompatibilní vrstvu umožňující běh plnohodnotných X11 desktopových prostředí s využitím komponent z Waylandu. Cílem je nakonec nahradit klasický server X.Org, a tím snížit zátěž údržby aplikací X11.

    Ladislav Hagara | Komentářů: 0
    včera 13:33 | Nová verze

    Byla vydána nová verze 6.18 živé linuxové distribuce Tails (The Amnesic Incognito Live System), jež klade důraz na ochranu soukromí uživatelů a anonymitu. Nově se lze k síti Tor připojit pomocí mostu WebTunnel. Tor Browser byl povýšen na verzi 14.5.5. Thunderbird na verzi 128.12.0. Další změny v příslušném seznamu.

    Ladislav Hagara | Komentářů: 0
    24.7. 14:33 | IT novinky

    Meta představila prototyp náramku, který snímá elektrickou aktivity svalů (povrchová elektromyografie, EMG) a umožňuje jemnými gesty ruky a prstů ovládat počítač nebo různá zařízení. Získané datové sady emg2qwerty a emg2pose jsou open source.

    Ladislav Hagara | Komentářů: 0
    24.7. 14:22 | Nová verze

    Byla vydána (𝕏) nová verze 25.7 open source firewallové a routovací platformy OPNsense (Wikipedie). Jedná se o fork pfSense postavený na FreeBSD. Kódový název OPNsense 25.7 je Visionary Viper. Přehled novinek v příspěvku na fóru.

    Ladislav Hagara | Komentářů: 0
    24.7. 13:33 | IT novinky

    Před 40 lety, 23. července 1985, společnost Commodore představila první počítač Amiga. Jednalo se o počítač "Amiga od Commodore", jenž byl později pojmenován Amiga 1000. Mělo se jednat o přímou konkurenci počítače Apple Macintosh uvedeného na trh v lednu 1984.

    Ladislav Hagara | Komentářů: 2
    24.7. 06:00 | IT novinky

    T‑Mobile USA ve spolupráci se Starlinkem spustil službu T-Satellite. Uživatelé služby mohou v odlehlých oblastech bez mobilního signálu aktuálně využívat satelitní síť s více než 650 satelity pro posílání a příjem zpráv, sdílení polohy, posílání zpráv na 911 a příjem upozornění, posílání obrázků a krátkých hlasových zpráv pomocí aplikace Zprávy Google. V plánu jsou také satelitní data.

    Ladislav Hagara | Komentářů: 9
    23.7. 21:55 | Komunita

    Společnost Proxmox Server Solutions stojící za virtualizační platformou Proxmox Virtual Environment věnovala 10 000 eur nadaci The Perl and Raku Foundation (TPRF).

    Ladislav Hagara | Komentářů: 2
    23.7. 21:22 | Bezpečnostní upozornění

    Byla vydána nová verze 2.4.65 svobodného multiplatformního webového serveru Apache (httpd). Řešena je bezpečnostní chyba CVE-2025-54090.

    Ladislav Hagara | Komentářů: 0
    Kolik tabů máte standardně otevřeno ve web prohlížeči?
     (29%)
     (25%)
     (5%)
     (5%)
     (5%)
     (2%)
     (2%)
     (27%)
    Celkem 131 hlasů
     Komentářů: 16, poslední včera 15:31
    Rozcestník

    Program na výpis prvočísel

    16.9.2007 19:52 | Přečteno: 17486× | Programy

    Když jsem se loni rozhodoval, jaké semináře si zvolit do 4. ročníku, programování byla moje jasná volba.

    Měl jsem štěstí, že se našlo víc lidí a seminář se otevřel. Hned v první hodině jsme dostali za úkol napsat algoritmus pro výčet prvočísel, následně zakreslit jeho vývojový diagram a ti co už měli zkušenosti s programováním ho i napsat v nějakém programovacín jazyku. Tento úkol se mi velice líbil, a tak jsem se hned pustil do práce. První verze programu jsem měl za chvíli a fungovali dobře, jako jazyk jsem zvolil C++. Jedinou nevýhodou byla rychlost, kdyý jsem chtěl vypsat všechna prvočísla do 100 000, tak to trvalo +- 1 minutu. A tak jsem začal optimalizovat kód, nejprve sem dělal jen drobné změny, potom použil při kompilaci přepínač -O3, čímž jsem se dostal asi na dobu 32s pro prvočísla do 100 000.

    Neuspokojilo mě to, ačkoliv to znamenalo zrychlení zhruba o 50%, a tak jsem nakonec celý program úplně přepsal a zvolil jinačí způsob hledání prvočísel. Což se ukázalo jako dobré řešení. Doba pro výčet prvočísel do 100 000 byla kolem 0.900s a po par optimalizacich jsem se dostal na 0.005s. Nakonec jsem se rozhodl to napsat i v ruby, ve kterem to jede sice pomaleji, ale i tak je to rychlejsi nez muj prvni navrh v C++.

    Celkově z toho mám dobrý pocit, ale věřím, že by se to dalo ještě vylopšit, ačkoliv už nevím jak. No jediný problém jsou nároky na pamět pro výčet prvočísel do 1 000 000 000 si to vezme skoro 1GB paměti :-D

    Kód v C++:

    #include <cmath>
    #include <iostream>
    using namespace std;
    
    typedef unsigned long long myInt;
    
    int main ( int argc, char *argv[] ){
            myInt nRozsah = 100000;
            //cout << "Zadejte rozsah:" << endl;
            //cin >> nRozsah;
            nRozsah++;
            bool *polePravda = new bool[ nRozsah];
    
            long op = long(sqrt(nRozsah));
            for ( myInt j = 3; j < op; j += 2 ){
                            if(polePravda[j]==false){
                            for ( myInt k = j; k <= nRozsah/j; k += 2 ){
                                    polePravda[ k * j ] = true;
                            }
    
                            }
            }
            cout << 2 << endl;
            for ( myInt l = 3; l < nRozsah; l += 2 ){
                    if ( polePravda[l] == false){
                            cout << l;
                    }
            }
            return 0;
    
    
    Kód v Ruby:
    #!/usr/bin/env ruby
    
    $KCODE = 'UTF-8'
    
    require 'mathn'
    
    
    nRozsah = 1000000
    polePravda = Array.new(nRozsah, 0)
    op = Math.sqrt(nRozsah)
    j = 3
             loop { 
      
                    if polePravda[j] == 0 then 
                            k = j
                            loop do
                                    polePravda[ k * j ] = 1
                                    k +=2
                                    break if k > nRozsah/j 
                            end
                    end
      
                    j += 2
                    break if j >= op
            }
            x = 3
            loop {
                    if polePravda[x] == 0 then
                            puts x
                    end
                    x += 2
                    break if x > nRozsah
            }
    

    Jinak časy byly meřeny pomocí příkazu time a výstup byl přesměrován do souboru.

           

    Hodnocení: 100 %

            špatnédobré        

    Tiskni Sdílej: Linkuj Jaggni to Vybrali.sme.sk Google Del.icio.us Facebook

    Komentáře

    Diskuse byla administrátory uzamčena

    16.9.2007 20:31 Käyttäjä 11133 | skóre: 58 | blog: Ajattelee menneisyyttä
    Rozbalit Rozbalit vše Re: Program na výpis prvočísel
    Právě kvůli velké paměťové náročnosti se nemůže tento algoritmus používat v kryptografických aplikacích :-)
    16.9.2007 20:56 andree | skóre: 39 | blog: andreeeeelog
    Rozbalit Rozbalit vše Re: Program na výpis prvočísel
    prave nedavno som o tom rozmyslal, ako asi zistuju programy prvocisla, ktore maju tak 1000 cifier.. prvocisla z tabulky sa na asymetricke sifrovanie asi pouzivat nedaju - zo zrejmych dovodov :-)))
    16.9.2007 21:02 Käyttäjä 11133 | skóre: 58 | blog: Ajattelee menneisyyttä
    Rozbalit Rozbalit vše Re: Program na výpis prvočísel
    Generují náhodné číslo pro něž ověří je-li prvočíslo, pokud není generují znovu.
    16.9.2007 21:03 Käyttäjä 11133 | skóre: 58 | blog: Ajattelee menneisyyttä
    Rozbalit Rozbalit vše Re: Program na výpis prvočísel
    Tedy pseudonáhodné :-)
    16.9.2007 21:09 Ladicek | skóre: 28 | blog: variace | Havlíčkův brod
    Rozbalit Rozbalit vše Re: Program na výpis prvočísel
    Generují náhodné číslo pro něž ověří je-li
    s jistou pravděpodobností
    prvočíslo, pokud není generují znovu.
    :-)
    Ještě na tom nejsem tak špatně, abych četl Viewegha.
    16.9.2007 21:18 Käyttäjä 11133 | skóre: 58 | blog: Ajattelee menneisyyttä
    Rozbalit Rozbalit vše Re: Program na výpis prvočísel
    jj.
    16.9.2007 22:10 andree | skóre: 39 | blog: andreeeeelog
    Rozbalit Rozbalit vše Re: Program na výpis prvočísel
    ahaaa, no hlavne to ma zaujimalo, ako sa overi ze to je prvocislo... toto normalne dava zmysel :o)
    17.9.2007 07:20 happy barney | skóre: 34 | blog: dont_worry_be_happy
    Rozbalit Rozbalit vše Re: Program na výpis prvočísel
    z prednášok si pamatam, že cislo sa negeneruje náhodne ale ako ((prvočíslo * prvočíslo) + 1)
    Na testovanie tam bolo niečo, čo si už presne nepamätám, niečo na spôsob: pravdepodobnosť, že je toto prvočíslo = 1/2 ^ počet testov (detaily by som musel hľadať)
    17.9.2007 08:23 Tom.š Ze.le.in | skóre: 21 | blog: tz
    Rozbalit Rozbalit vše Re: Program na výpis prvočísel
    Doporučuji třeba Handbook of Applied Cryptography (stáhnutelné z webu jako pdf), tam tohle je celkem detailně a přístupně popsané
    17.9.2007 23:38 elviin | skóre: 29 | blog: elviin | Plzeň-Praha
    Rozbalit Rozbalit vše Re: Program na výpis prvočísel
    je nejakej teorem, kterej rika, ze v blizkosti nahdone zvoleneho cisla se s jistou vypocitalenou ppsti vyskytuje prvocislo. ted si nemuzu vzpomenout, jak se nazyva.

    Btw jsem videl (ted nemuzu najit stranku) jakysi postup, kde se prvocisla zanesla do grafu - coz byla spirala z celych cisel. Po odstraneni neprvocisel se projevila provcisla. Ta se vyskytovala na urcitych krivkach vychazejicich z pocatku grafu. Takze se tim elimoval prohledavany prostor celych kladnych cisel.

    Btw2 slysel nekdo o neuronovych sitich, ktery by se daly naucit pro urcovani prvocisla?
    18.9.2007 16:26 zero
    Rozbalit Rozbalit vše Re: Program na výpis prvočísel
    Jmenuje se to prvočíselná věta, podle které je počet prvočísel menších x přibližně x/ln(x). Z ní snadno plyne že pro dostatečně velká x je pravděpodobnost prvočísla kolem x rovna 1/ln(x). Tedy např pro x = 1000000 je asi každé 14-té číslo prvočíslem.
    16.9.2007 21:30 Martin Tůma | skóre: 39 | blog: RTFM | Praha
    Rozbalit Rozbalit vše Re: Program na výpis prvočísel
    věřím, že by se to dalo ještě vylopšit, ačkoliv už nevím jak

    Wikipedie se u Eratosthenova síta zmiňuje o urychlování pomocí kruhové faktorizace, tak to můžeš zkusit ;-)

    Každý má právo na můj názor!
    16.9.2007 21:35 kozzi | skóre: 55 | blog: vse_o_vsem | Pacman (Bratrušov)
    Rozbalit Rozbalit vše Re: Program na výpis prvočísel
    díky kouknu se na to
    Linux je jako mušketýři "jeden za všechny, všichni za jednoho"
    16.9.2007 21:39 kozzi | skóre: 55 | blog: vse_o_vsem | Pacman (Bratrušov)
    Rozbalit Rozbalit vše Re: Program na výpis prvočísel
    No anglicky sice neumim nijak bravurne, ale zda se mi ze muj program +- toto pouziva
    Linux je jako mušketýři "jeden za všechny, všichni za jednoho"
    16.9.2007 22:06 Martin Tůma | skóre: 39 | blog: RTFM | Praha
    Rozbalit Rozbalit vše Re: Program na výpis prvočísel

    Tvůj program je ± Eratosthenovo síto, to co je na wikipedii pod heslem wheel factorization je ale jedna z metod rychlých odhadů prvočíselnosti. (podobné používají třeba kryptografické programy při generování klíčů - teprve pokuď projde číslo některým z těchto testů, zkouší se dál, jestli je to skutečně prvočíslo)

    Každý má právo na můj názor!
    17.9.2007 00:26 Deleted [8409] | skóre: 14 | blog: darkblog
    Rozbalit Rozbalit vše Re: Program na výpis prvočísel
    Nároky na pamět snížíte i tím, že si uděléte nějaké bitové pole. Používáte sice bool[N], ale ono je to jen obyčejný char. Bitovým polem snížíte nároky 8x.
    17.9.2007 01:21 Ivanhoej | skóre: 26 | blog: ss2_Debian | Bratislava
    Rozbalit Rozbalit vše Re: Program na výpis prvočísel
    Toto je sice pomale no ale kolko pisania to usetri :)
    #!/usr/bin/env ruby
    nRozsah = 10000
    puts (2..nRozsah).inject((2..nRozsah).to_a) {|res, i| res.select{|n|n==i||n%i!=0} }
    
    17.9.2007 08:27 thingie
    Rozbalit Rozbalit vše Re: Program na výpis prvočísel
    Hm, neříkejte mi, že by to v tom ruby nešlo napsat hezčejc než tímhle ošklivým přepisem céčkového kódu, to je hrozně o ničem.
    17.9.2007 09:10 kozzi | skóre: 55 | blog: vse_o_vsem | Pacman (Bratrušov)
    Rozbalit Rozbalit vše Re: Program na výpis prvočísel
    jj šlo, taky to tak někde mám, ale nebylo to tak výkoné.
    Linux je jako mušketýři "jeden za všechny, všichni za jednoho"
    17.9.2007 08:46 Tom.š Ze.le.in | skóre: 21 | blog: tz
    Rozbalit Rozbalit vše Re: Program na výpis prvočísel
    Nevím jak je definováno v C++ polePravda, ale pokud to bere tolik paměti co říkáte, tak by se to zřejmě dalo triválně vylepšit přepisem do bitového pole s osminovou paměťovou náročností. Vynechat v poli sudá čísla - další polovina paměti, možná vynechat 6k+3 - další úspora. Ale další podobné úspory (a možná ani tahle) už asi nemají cenu a je lepší přejít na sofistikovanější algoritmy.
    17.9.2007 18:42 X3 | blog: Půlnoční blog
    Rozbalit Rozbalit vše Re: Program na výpis prvočísel
    Ted si vzpominam, ze jsme ve skole pred 2 lety mely taky jako projekt udelat program na vypocet prvocisel... Jen jsme meli vypocitat prvocisla do 15 000 000 do 4 sekund :) A slo to :)
    Kuk :-)
    17.9.2007 18:44 X3 | blog: Půlnoční blog
    Rozbalit Rozbalit vše Re: Program na výpis prvočísel
    Jo jeste bych uvedl ze v pameti to zabiralo +- 12MB (bitove pole pres char) a pouzito bylo Erasthenovo sito :)
    Kuk :-)
    17.9.2007 19:01 foo
    Rozbalit Rozbalit vše Re: Program na výpis prvočísel
    Bez uvedeni OS, programovaciho jazyka a typu hardware atd. mi to prijde jako bohapuste chvastani. :-D
    17.9.2007 19:49 X3 | blog: Půlnoční blog
    Rozbalit Rozbalit vše Re: Program na výpis prvočísel
    Dobre, ja myslel, ze kdyz jsme na abclinuxu tak jsou lidi natolik inteligentni, ze kdyz neni uveden os tak se jedna o linux.

    Takze jsem to vyhrabal - nejednalo se o prvocisla do 10M, ale do 100M, jelo to i na win, i na linuxu, proste je to obyc C, za 4s to zvladal i muj 1,5GHz stroj s windows, skolni 64bit 2Ghz to zvladal za 3,2s tady mas teda zdrojak

    #include <stdio.h> #include <math.h> #include "error.h"

    #define N 100000000LU

    #define UI \ (unsigned int) #define SIZE(num) \ (num / (sizeof(long) * 8) + 2) #define BITS \ (sizeof(long) * 8) #define BITPOS(index) \ ((index % BITS) + 1) #define ArrayPos(index) \ (UI index/BITS+1) #define OutArrayError(pole, index) \ Error("Index %ld mimo rozsah 0..%ld", (long) index, (long) pole[0]) #define OutArray(pole, index) \ (index < 0 || index > pole[0]) ? OutArrayError(pole, index),0 :

    #define BitArray(jmeno_pole, velikost) \ unsigned long jmeno_pole[SIZE(velikost)] = {0}; \ jmeno_pole[0] = velikost

    #ifndef USE_INLINE #define GetBitIn(jmeno_pole, index) \ (jmeno_pole[ArrayPos(index)] & (1LU << BITPOS(index)) ? 1 : 0)

    #define GetBit(jmeno_pole, index) \ OutArray(jmeno_pole, index) GetBitIn(jmeno_pole, index)

    #define SetBit(pole, index, vyraz) \ if(!(index >= 0U && index <= pole[0]))\ OutArrayError(pole, index);\ if(vyraz != 0) \ pole[ArrayPos(index)] |= 1LU << BITPOS(index); \ else \ pole[ArrayPos(index)] ^= GetBit(pole, index) << BITPOS(index)

    #endif

    #ifdef USE_INLINE inline int GetBit(unsigned long pole[], long index) { if(index < 1 || index > pole[0]) Error("Index %ld mimo rozsah 0..%ld", (long) index, (long) pole[0]);

    return pole[ArrayPos(index)] & ((1LU << BITPOS(index)) ? 1 : 0); }

    inline void SetBit(unsigned long pole[], long index, int vyraz) { if(index < 0 || index > pole[0]) Error("Index %ld mimo rozsah 0..%ld", (long) index, (long) pole[0]); if(vyraz != 0) pole[ArrayPos(index)] |= 1LU << BITPOS(index); else pole[ArrayPos(index)] ^= GetBit(pole, index) << BITPOS(index); } #endif int main() {

    BitArray(eSito, N); SetBit(eSito, 0, 1); SetBit(eSito, 1, 0);

    for(unsigned int i = 2; i < N; i++) { SetBit(eSito, i, 0); }

    unsigned long sqrt_n = sqrt(N);

    for(unsigned int i = 2; i < sqrt_n; i++) { if(GetBit(eSito, i) == 0) { for(unsigned int j = i * i; j < N; j += i) { SetBit(eSito, j, 1); } } }

    int count = 0; int prvocisla[10] = {0};

    for(unsigned int i = N - 1; i > 1; i--) { if(GetBit(eSito, i) == 0) { prvocisla[count] = i; count += 1; if(count == 10) break; } }

    for(int i = 0; i < 10; i++) printf("%d\n", prvocisla[9-i]);

    return 0; }

    Funkcni by to byt melo, nejrychlejsi je to pri pouziti maker, inlive funkce jsou tam pro porovnani (bylo v zadani) a je to cca o 1s pomalejsi. Jeste dodam, ze se vypisuje jen poslednich 10prvocisel, vypisovat vsechno by bylo pochopitelne znacne pomalejsi, kuli io operacim.
    Kuk :-)
    17.9.2007 21:22 Tom.š Ze.le.in | skóre: 21 | blog: tz
    Rozbalit Rozbalit vše Re: Program na výpis prvočísel
    Bohapusté chvástání? Mně to přijde dost skromné, zkuste to - není na to potřeba ani makroassembler zvaný C - do těch 15M za daných podmínek (vypis poslednich deseti) to zvládne přímočará implementace třeba v Common Lispu (sbcl) na pár let starém Athlonu 1700+ pod sekundu.

    Do těch 100M to trvalo už sekund sedm, uznávám...
    ISSN 1214-1267   www.czech-server.cz
    © 1999-2015 Nitemedia s. r. o. Všechna práva vyhrazena.