010 Ciurul lui Eratosthenes

[•filipb]

Aici puteti discuta despre problema Ciurul lui Eratosthenes.

[•Prostu]

Daca limita lui N era putin mai mica, pe undeva pe la 960000, problema asta se putea rezolva si pe Borland C++ 3.1.
In primul rand nu ai nevoie de numerele pare, pentru ca 2 este singurul numar par prim. Dupa aceea nu ai nevoie decat de un singur bit pentru a sti daca numarul curent este prim. Putea fi implementat deci folosind un singur vector unsigned char de 60000 folosindu-se desigur operatiile pe biti. Fiecarui numai impar i ii corespundea bitul i / 2 din vector, si fiecarui bit i din vector ii corespundea numarul 2 * i + 1. Daca imi aduc bine aminte, ciurul implementat astfel intra chiar si pe Borland in 0.5 secunde.

[•sigrid]

Mi se pare putin, numai putin, exagerat faptul ca 8 din 10 teste pica daca in fisier se afiseaza mai mult de 1000 de numere.
Prioritatea acestei probleme ar trebui sa fie generarea ciurului, nu numarul de elemente puse in fisier.

[•filipb]

Fisierul de iesire contine 1000 de numere pentru a evita folosirea fisierelor de dimensiuni foarte mari. Primele 1000 de numere prime se ating pentru N aproximativ 10000, si pentru N 10000 merge o solutie si in O(NsqrtN), care nu ar trebui sa ia mai mult de 20-30 de puncte .

[•domino]

Cred ca astfel de restrictii sunt chiar impotriva spiritului arhivei educationale. Nu cred ca ar fi fost o problema prea mare daca se afiseaza toate numerele prime sau eventual, se poate cere doar numarul lor.

[•Cosmin]

Nici mie nu mi-a placut chestia cu 1000 de numere, era deajuns numarul de nr prime. Vroiam sa bag varianta de ciur optimizat pe biti, si dupa ce am vazut ca mai trebuie sa afisezi si altceva am lasat-o balta.

[•bogdan2412]

Ajungeti sa considerati afisarea cea mai grea parte din problema ... Sa afisezi numerele nu ia mai mult de 3 linii...

Oricum daca se modifica enuntul acum tb reevaluate 23 de pagini de surse dintre care toti cei care au luat 100 pana acum o sa ia 20...

[•Protoman]

Ati putea cere sa se afiseze minim 1000

[•devilkind]

daca s-ar cere numai cate sunt prime, atunci sursele de 100 ar putea lua 100 in continuare.

[•filipb]

La aceasta problema s-a modificat enuntul si s-au schimbat testele. In consecinta a fost facuta o reevaluare. Ne cerem scuze pentru eventualele neplaceri.

[•vlad_oltean]

La aceasta problema s-a modificat enuntul si s-au schimbat testele. In consecinta a fost facuta o reevaluare. Ne cerem scuze pentru eventualele neplaceri.

acum m-am prins si eu... nu pricepeam de ce am 0p

[•zalman]

pls need help! am incercat sa o fac ...si pe testele mele imi merge bine...imi da o eroarea la compilare din cauza batranului borland 3.1 (array size to large) insa cand am trimis sursa am modificat marimea vectorului la 2000004 (char) si tot imi da ceva eroarea.habar nu am despre ce e vorba

"eroare de compilare in evaluator: In file included from /usr/include/c++/4.2/backward/fstream.h:31, from user.cpp:1: /usr/include/c++/4.2/backward/backward_warning.h:32:2: warning: #warning This file includes at least one deprecated or antiquated header. Please consider using one of the 32 headers found in section 17.4.1.2 of the C++ standard. Examples include substituting the <X> header for the <X.h> header for C++ includes, or <iostream> instead of the deprecated header <iostream.h>. To disable this warning use -Wno-deprecated. user.cpp: In function 'int main()': user.cpp:12: error: name lookup of 'i' changed for new ISO 'for' scoping user.cpp:10: error: using obsolete binding at 'i'"

 

[•sima_cotizo]

Cod:

for (int i=2;i<=n;++i)   
    ciur[i]=1;   
  
for (i=2;i<=n;++i)

Aici e problema ta. In al doilea for nu mai stie cine e i-ul pe care mai sus l-ai declarat local. Asta merge in "batranul Borland", dar nu si in gcc. Pune i-ul la globale sau local in main si va merge!

[•tm_radu]

Incearca sa inlocuiesti

Cod:

#include <fstream.h>

cu

Cod:

#include <fstream>
using namespace std;

[•Mishu91]

O alternativa pentru ciurul pe biti(de departe cea mai buna modalitate, atat ca timp, cat si ca memorie), ar fi folosirea in loc de vectori de tip char vectorii de tip bool din STL. Avantaju este ca fiecare element este memorat pe un singur bit, si astfel se reduce mult memoria si timpul(aproape ca la ciurul pe biti... aici este evaluarea http://infoarena.ro/job_detail/187508), iar implementarea este aproape identica implementarii clasice.

L.E.: Cu ceva optimizari se poate ajunge la aceleasi performante de timp si memorie cu metoda pe biti http://infoarena.ro/job_detail/187607

[•wefgef]

Incearca si cu bitset din STL - sunt curios cum merge. Vector de bool este dubios si se pare ca nu are mare viitor: http://en.wikipedia.org/wiki/Boolean_datatype#C.2B.2B. Oricum, deocamdata se pare ca face treaba

[•Mishu91]

Ca uns merge Super tare... scoate timpi kiar mai buni decat cu vector <bool> http://infoarena.ro/job_detail/187628

[•Vlad_fisca]

 Cam in cat timp imi afiseaza cu ciurul numerele prime din intervalul [1..64 000],folosind Ciurul lui Eratostene?

[•devilkind]

mai putin 0.1 secunde, ciurul lui erathostene daca e facut cum trebuie e foarte rapid, are complexitate O(N*ln N) daca nu ma inseala cunostintele de matematica.

[•Vlad_fisca]

 Mersi,Savin
 Se pot obtine mai mult de 30 de puncte pe algoritmul brut?sau e nevoie de optimizari?

[•devilkind]

nush exact ce intelegi prin algoritmul brut.
Uite aici un articol despre cum poti sa afli numerele prime folosind ciurul lui eratostene

[•Florian]

Si in plus, ai acces la sursele celorlalti. Asadar, iti va fi mai usor sa inveti cum se face ciurul. Succes!   

[•Cosmin]

@Tiberiu Dupa cum ziceam aici http://infoarena.ro/blog/intrebare-scurta ciurul are complexitate O(n log log n)

[•k_ounu_eddy]

Am o intrebare.Am citit si articolul cu ciurul lui Erathostenes,m-am uitat putin si pe codul cu optimizari pe biti,si am vazut ca foloseati peste tot tipul char.Asta complica mult lucrurile zic eu,nu ar fi mai simplu sa folosim tipul bool? Bineinteles,la OJI,ONI etc ii folositor acest lucru,ca nu ai bool acolo,dar aici unde se foloseste gcc e mai simplu,nu?

[•wefgef]

Un bool ocupa 8 biti (cel putin in C/C++, nu stiu in Java) si iti permita sa stochezi o singura valoare. Daca folosesti char atunci poti stoca pe 8 biti 8 valori, optimizand la maxim memoria folosita.

P.S.: La ONI se compileaza sub linux, in gcc .