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 16:00 | IT novinky

    Ministerstvo průmyslu a obchodu (MPO) ve spolupráci s Národní rozvojovou investiční (NRI) připravuje nový investiční nástroj zaměřený na podporu špičkových technologií – DeepTech fond. Jeho cílem je posílit inovační ekosystém české ekonomiky, rozvíjet projekty s vysokou přidanou hodnotou, podpořit vznik nových technologických lídrů a postupně zařadit Českou republiku mezi země s nejvyspělejší technologickou základnou.

    … více »
    Ladislav Hagara | Komentářů: 0
    dnes 12:55 | Nová verze

    Radicle byl vydán ve verzi 1.5.0 s kódovým jménem Hibiscus. Jedná se o distribuovanou alternativu k softwarům pro spolupráci jako např. GitLab.

    Ladislav Hagara | Komentářů: 2
    dnes 03:22 | IT novinky

    Společnost OpenAI představila text-to-video AI model Sora 2 pro generování realistických videí z textového popisu. Přesnější, realističtější a lépe ovladatelný než předchozí modely. Nabízí také synchronizované dialogy a zvukové efekty.

    Ladislav Hagara | Komentářů: 4
    včera 23:11 | Nová verze

    UBports, nadace a komunita kolem Ubuntu pro telefony a tablety Ubuntu Touch, vydala Ubuntu Touch 24.04-1.0, tj. první stabilní vydání založené na Ubuntu 24.04 LTS.

    Ladislav Hagara | Komentářů: 0
    včera 21:00 | Komunita

    Rakouská armáda přechází na LibreOffice. Ne kvůli licencím (16 000 počítačů). Hlavním důvodem je digitální suverenita. Prezentace v pdf z LibreOffice Conference 2025.

    Ladislav Hagara | Komentářů: 23
    včera 12:44 | Bezpečnostní upozornění

    Národní úřad pro kybernetickou a informační bezpečnost (NÚKIB) upozorňuje na sérii kritických zranitelností v Cisco Adaptive Security Appliance (ASA) a Firepower Threat Defense (FTD) a Cisco IOS, CVE-2025-20333, CVE-2025-20363 a CVE-2025-20362. Zneužití těchto zranitelností může umožnit vzdálenému neautentizovanému útočníkovi spustit libovolný kód (RCE). Společnost Cisco uvedla, že si je vědoma aktivního zneužívání těchto zranitelností.

    Ladislav Hagara | Komentářů: 16
    včera 12:11 | IT novinky

    Ochrana uživatelů a zároveň příznivé podmínky pro rozvoj umělé inteligence (AI). Ministerstvo průmyslu a obchodu (MPO) připravilo minimalistický návrh implementace evropského nařízení o umělé inteligenci, tzv. AI aktu. Český zákon zajišťuje ochranu občanům a bezpečné používání AI, ale zároveň vytváří pro-inovační prostředí, ve kterém se může AI naplno rozvíjet, firmy mohou využít jeho potenciál a nebudou zatíženy zbytečnou administrativou. Návrh je nyní v meziresortním připomínkovém řízení.

    Ladislav Hagara | Komentářů: 8
    včera 05:11 | Komunita

    Dle plánu Linus Torvalds odstranil souborový systém bcachefs z mainline Linuxu. Tvůrce bcachefs Kent Overstreet na Patreonu informuje, že bcachefs je nově distribuován jako DKMS modul.

    Ladislav Hagara | Komentářů: 2
    29.9. 17:44 | IT novinky

    PIF, Silver Lake a Affinity Partners kupují videoherní společnost Electronic Arts (EA) za 55 miliard dolarů (1,14 bilionu korun).

    Ladislav Hagara | Komentářů: 2
    29.9. 16:33 | Pozvánky

    Konference LinuxDays 2025 proběhne již tento víkend 4. a 5. října v Praze v areálu ČVUT v Dejvicích na FIT. Konference znamená desítky přednášek a workshopů, zástup zajímavých osobností, místo pro setkání, spoustu nových nápadů a informací a stánky řady různých projektů: Fedora, openSUSE, vpsFree.cz, Mozilla, MacGyver - bastlíři SH, OpenAlt a mnoho dalších. Účast na konferenci je zdarma.

    Ladislav Hagara | Komentářů: 2
    Jaké řešení používáte k vývoji / práci?
     (39%)
     (48%)
     (12%)
     (14%)
     (17%)
     (14%)
     (18%)
     (14%)
     (14%)
    Celkem 146 hlasů
     Komentářů: 9, poslední 24.9. 17:28
    Rozcestník

    Program na výpis prvočísel

    16.9.2007 19:52 | Přečteno: 17491× | 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.