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í
×
    dnes 15:22 | IT novinky

    Masivní výpadek elektrického proudu zasáhl velkou část České republiky. Hasiči vyjížděli k většímu počtu lidí uvězněných ve výtazích. Výpadek se týkal zejména severozápadu republiky, dotkl se také Prahy, Středočeského nebo Královéhradeckého kraje. Ochromen byl provoz pražské MHD, linky metra se už podařilo obnovit. Výpadek proudu postihl osm rozvoden přenosové soustavy, pět z nich je nyní opět v provozu. Příčina problémů je však stále neznámá. Po 16. hodině zasedne Ústřední krizový štáb.

    Ladislav Hagara | Komentářů: 8
    dnes 02:33 | Nová verze

    Po více než roce vývoje od vydání verze 5.40 byla vydána nová stabilní verze 5.42 programovacího jazyka Perl (Wikipedie). Do vývoje se zapojilo 64 vývojářů. Změněno bylo přibližně 280 tisíc řádků v 1 500 souborech. Přehled novinek a změn v podrobném seznamu.

    Ladislav Hagara | Komentářů: 2
    dnes 01:33 | Nová verze

    Byla vydána nová stabilní verze 7.5 webového prohlížeče Vivaldi (Wikipedie). Postavena je na Chromiu 138. Přehled novinek i s náhledy v příspěvku na blogu.

    Ladislav Hagara | Komentářů: 0
    včera 16:33 | Zajímavý software

    Sniffnet je multiplatformní aplikace pro sledování internetového provozu. Ke stažení pro Windows, macOS i Linux. Jedná se o open source software. Zdrojové kódy v programovacím jazyce Rust jsou k dispozici na GitHubu. Vývoj je finančně podporován NLnet Foundation.

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

    Byl vydán Debian Installer Trixie RC 2, tj. druhá RC verze instalátoru Debianu 13 s kódovým názvem Trixie.

    Ladislav Hagara | Komentářů: 0
    včera 03:33 | Komunita

    Na čem pracují vývojáři webového prohlížeče Ladybird (GitHub)? Byl publikován přehled vývoje za červen (YouTube).

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

    Libreboot (Wikipedie) – svobodný firmware nahrazující proprietární BIOSy, distribuce Corebootu s pravidly pro proprietární bloby – byl vydán ve verzi 25.06 "Luminous Lemon". Přidána byla podpora desek Acer Q45T-AM a Dell Precision T1700 SFF a MT. Současně byl ve verzi 25.06 "Onerous Olive" vydán také Canoeboot, tj. fork Librebootu s ještě přísnějšími pravidly.

    Ladislav Hagara | Komentářů: 0
    včera 01:33 | Komunita

    Licence GNU GPLv3 o víkendu oslavila 18 let. Oficiálně vyšla 29. června 2007. Při té příležitosti Richard E. Fontana a Bradley M. Kuhn restartovali, oživili a znovu spustili projekt Copyleft-Next s cílem prodiskutovat a navrhnout novou licenci.

    Ladislav Hagara | Komentářů: 0
    2.7. 16:55 | Nová verze

    Svobodný nemocniční informační systém GNU Health Hospital Information System (HIS) (Wikipedie) byl vydán ve verzi 5.0 (Mastodon).

    Ladislav Hagara | Komentářů: 0
    2.7. 16:22 | Komunita

    Open source mapová a navigační aplikace OsmAnd (OpenStreetMap Automated Navigation Directions, Wikipedie, GitHub) oslavila 15 let.

    Ladislav Hagara | Komentářů: 1
    Jaký je váš oblíbený skriptovací jazyk?
     (59%)
     (28%)
     (7%)
     (2%)
     (0%)
     (1%)
     (3%)
    Celkem 352 hlasů
     Komentářů: 16, poslední 8.6. 21:05
    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.