Program na výpis prvočísel (diskuse)

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