Program na výpis prvočísel

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

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.

       

Komentáře

Diskuse byla administrátory uzamčena

[Käyttäjä 11133]

Právě kvůli velké paměťové náročnosti se nemůže tento algoritmus používat v kryptografických aplikacích

[andree]

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 ))

[Käyttäjä 11133]

Generují náhodné číslo pro něž ověří je-li prvočíslo, pokud není generují znovu.

[Käyttäjä 11133]

Tedy pseudonáhodné

[Ladicek]

Generují náhodné číslo pro něž ověří je-li

s jistou pravděpodobností

prvočíslo, pokud není generují znovu.

[Käyttäjä 11133]

jj.

[andree]

ahaaa, no hlavne to ma zaujimalo, ako sa overi ze to je prvocislo... toto normalne dava zmysel :o)

[happy barney]

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ť)

[Tom.š Ze.le.in]

Doporučuji třeba Handbook of Applied Cryptography (stáhnutelné z webu jako pdf), tam tohle je celkem detailně a přístupně popsané

[elviin]

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?

[zero]

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.

[Martin Tůma]

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

[kozzi]

díky kouknu se na to

[kozzi]

No anglicky sice neumim nijak bravurne, ale zda se mi ze muj program +- toto pouziva

[Martin Tůma]

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)

[Deleted [8409]]

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.

[Ivanhoej]

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} }

[thingie]

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.

[kozzi]

jj šlo, taky to tak někde mám, ale nebylo to tak výkoné.

[Tom.š Ze.le.in]

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.

[X3]

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 :)

[X3]

Jo jeste bych uvedl ze v pameti to zabiralo +- 12MB (bitove pole pres char) a pouzito bylo Erasthenovo sito :)

[foo]

Bez uvedeni OS, programovaciho jazyka a typu hardware atd. mi to prijde jako bohapuste chvastani.

[X3]

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.

[Tom.š Ze.le.in]

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...