infoarena

Aici puteti discuta despre problema Ciurul lui Eratosthenes (http://infoarena.ro/problema/ciur).

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.

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.

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

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.

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.

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

Ati putea cere sa se afiseze minim 1000 :-k

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

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

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'"

 ](*,)

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!

Incearca sa inlocuiesti

cu

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

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

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

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

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.

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

nush exact ce intelegi prin algoritmul brut.
Uite aici un articol despre cum poti sa afli numerele prime folosind ciurul lui eratostene (http://infoarena.ro/ciurul-lui-erathostene)

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

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

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?

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

Bool in gcc nu ocupa doar 1 bit?

Nu, ocupa 8. Poti sa vezi dimensiunea unui tip de date cu sizeof(tip).

Nu reusesc sa imi dau seama de ce iau SIGSEGV pe sursa asta(primesc doar 20 p pe primele doua teste):

Dak ati putea sa imi spuneti unde gresesc...  :-'
Tx in advance ;))
[EDIT]:Problema era din cauza functiei memset,cred ca nu accepta valori prea mari...de asta luam sigsegv.Oricum nu m-am lamurit.Cert e ca dupa ce am scos functia memset() iau 100 p.

la memset trebuia sa pui memset(Prime, 0, sizeof(Prime)) fara sa imultesti cu alte minuni ca da pe dinafara :)

Ok,ai dreptate,am incercat si merge.
Dar uite ce zice aici http://www.cplusplus.com/reference/clibrary/cstring/memset.html (http://www.cplusplus.com/reference/clibrary/cstring/memset.html) .
Prin traducere ar veni asa:seteaza primii num bytes ai blocului de memorie...Dak pun acolo ultimul parametru sizeof(Prime),ar rezulta ca seteaza doar primii 4 bytes(aka Prime[0], Prime[1],Prime[2],Prime[3])
[EDIT]:Am facut niste teste in DJGPP ,si acuma imi da alte minuni.Si mai ziceti ca programarea nu are lucruri ciudate.Bine,pana la urma se datoreaza tot erorii umane,probabil ca are functia niste bug-uri ceva.Uitati un exemplu:
Puneti acolo la memset in loc de 2 orice vreti voi:1,2,3,4,100,1000 chiar si 0,si a[993] este egal to cu 0.

Pai da. Pt ca in *a, ai NULL peste tot, indiferent daca faci memset sau nu. Incearca sa pui memset(a,13,2) si o sa vezi ca a[993] va fi 0.  :)

Credeam ca doar variabilele globale sunt initializate cu 0,dar vad ca e si cazul alocarii dinamice.
In concluzie sa inteleg ca de fiecare data cand aloc dinamic,vectorii alocati sunt initializati cu 0?

daca puii .......
Nu mai e  0.......plus am incercat codul tau nu-ti afiseaza 0 (compilat sub VC++). Cand pui new int.... ti se aloca o zona de memorie libera, care contine nume aleatoriu ;)

Am observat ca ultimele mesaje contin informatii gresite despre alocarea dinamica a memorie si modul in care se foloseste functia memset.

Avand un pointer *p, pentru a aloca un vector de 1000 de elemente se procedeaza astfel:
sau:
Acum p contine adresa unui bloc rezervat de 1000 de elemente. Toate elentele p[0], p[1] pana la p[999] contin valori reziduale. Ele nu sunt initializate in nici un fel in nici unul din apelurile de mai sus. Putem spune ca au valori aleatoare. Se poate intampla ca toate aceste valori sa fie 0, dar asta e din pura intamplare. Diferenta intre malloc si new este ca ultimul apeleaza constructorul clasei pentru care se face instantierea, dar nu cred ca se pot supraincarca constructorii tipurilor predefinite.

Pentru a le initializa cu 0 folosind functia memset procedam in felul urmator:
Asta inseamna pentru compilatorul gcc de azi sa puna valoarea 0 pe 4000 de bytes pornind de la adresa pointata de p.

sizeof( variabila ) returneaza dimensiunea in bytes a tipului variabila asadar sizeof( p ) va returna pe gcc fie valoarea 4, fie valoarea 8, depinde de configuratia fiecaruia (iar pe borland valoarea 2), si este dimensiunea implicita a oricarui pointer (nu depinde de tipul obiectului pointat ci doar de compilator).
sizeof( int ) returneaza valoarea 4 in gcc si 2 in borland, sizeof( long ) returneaza valoarea 4 in gcc si 4 in borland.
Daca p ar fi declarat astfel:
atunci sizeof(p) ar returna valoarea 4000 pe gcc si 2000 pe borland (face diferenta).
Dar aveti grija la urmatorul caz:

memset( pointer, val_byte, dimensiune ) seteaza valoarea a dimensiune bytes pornind de la pointer cu valoarea val_byte.
De exemplu:
memset( p, 0, sizeof(p) ) ar seta pe 0 numai pe p[0] (in conditiile in care dimensiunea pointerului e 4, daca e 8 atunci ar seta si p[1])
memset(p, 0x3f, sizeof(int)) sau memset( p, 63, sizeof(int) ) ar seta p[0] cu valoarea cu 1061109567 sau 0x3f3f3f3f pentru ca sunt initializati 4 bytes cu valoarea 0x3f.

Imi zice si mie cineva  unde gresesc, adica imi apare KIll By Signel 11 chiar daca phi ii 3 000 001.
Sursa e  aici (http://infoarena.ro/job_detail/274543?action=view-source)

nu iti intra in memorie 3 000 000 de long-uri... si eu zic ca te complici la implementarea aia... nu am studiat-o prea atent dar 100% nu mergi pe marcarea numarului ca prim sau neprim ca in sursa oficiala, fiindca afisezi phi [ n ]...

uite o implementare mai simpla, ca si cea oficiala

http://infoarena.ro/job_detail/161860?action=view-source

in ok[] retin daca numarul este prim cu semnificatia:
ok[ i ]=0 ->numarul e prim
ok[ i ]=1 ->numarul nu e prim

Pai  daca ni se cere  numarul de numere prime pana la n, nu  calculam functia phi ??.....
3 000 000 am pus ca ma inerva ca tot apare   Kiiled by signel 11 ....... ](*,) ma scoate din sarite 

Pai daca ni se cere numarul de numere prime pana la n, ne folosim de indiciul evident din titlul problemei : Ciurul lui Eratosthenes.

Nu de la idee e problema, mie imi pare corecta, ci de la faptul ca aloci un vector de 3 milioane, de tip long, cand ai doar 3 mega memorie. Citeste cu atentie enuntul si restrictiile la probleme inainte de a implementa (uneori chiar inutil) ceva.

E simplu:
folositi o subrutina prim.E cea mai rapida cale.  :D

Si atunci de ce iei TLE? :P

Ce frumos ... am reusit sa scot in pascal memorie mai buna decat in c++  :thumbup: .

Fisier gresit!!!

Ce inseamna asta ?

Killed by signal 11(SIGSEGV).Ce vrea sa insemne? Am obtinut 40 de puncte numai...:

#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
bool a[1000001];
int i,j,n;
int main()
{
    ifstream f("ciur.in");
    ofstream g("ciur.out");
    f>>n;
    f.close();
    for(i=2;i<=trunc(sqrt(n));i++)
         if (a==0)
           { j=2;
           do
           { a[i*j]=1;
             j++;}
           while (j*i<n);
           }
       i=0;
       for(j=2;j<=n;j++)
      if (a[j]==0) i++;
      i--;
    g<<i;
    g.close();
    return 0;
}
   

Pardon, dupa cum ziceam primesti signal 11 cand vrei sa accesezi memorie nealocata, n-ul maxim in problema este 2000000, tu ai vectorul de 1000000

Multumesc.

Pentru testul 6, avem numarul 1356897, care este prim, dar in .ok acesta nu este luat in considerare.  Ar trebui modificat din "mai mici sau egale cu N." in "numerelor prime mai mici decat N."; Eu am luat 90 cu "<=" si 100 cu "<".(Sau e doar cazul meu:-??);

De ce esti atat de sigur ca e prim? Ti-l ia ca si prim fiindca ai "<" la for-ul cu care parcurgi multiplii.

Salut,
Poate sa imi spuna si mie cineva de ce primesc 0 puncte la urmatoarea sursa ? http://www.infoarena.ro/job_detail/1014982?action=view-source
Am testat si cu N = 15,485,863 (care e al 1.000.000 numar prim) si imi returneaza corect.  :-k

Cel mai probabil iti face overflow pow(i,2). Si mai indenteaza codul ala :)

nu cred. am mai incercat si alte surse, rezultatele sunt bune. m-am uitat si pe pagina cu teste si corespund. nu primesc TLE/SIGSEGV, doar "incorect".  ???

Ai dreptate. De fapt, nu foloseai bine fstream. Ori ii specifici faptul ca il folosesti pentru input ori pur si simplu il declari ca si ifstream.

asta era  :D =D&gt; multumesc mult!
pateam acelasi lucru si la alte rezolvari, si nu-mi putea explica de ce  :aha:

 ](*,)
Panarama

Salut!
Am rezolvat problema, dar nu stiu ce sa afisez, ma puteti ajuta?

 :banana: :banana: :banana: :banana: :banana: :banana: :banana: :banana: :banana: :banana: :banana: :banana:
merita -99 puncte