010 Ciurul lui Eratosthenes

[•k_ounu_eddy]

Bool in gcc nu ocupa doar 1 bit?

[•wefgef]

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

[•k_ounu_eddy]

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

Cod:

#include<stdio.h>
#include<string.h>

int n,cnt=0;
char *Prime;
//Prime[i]==1 => Prime[i] nu e prim
//am folosit optimizarile:
//nu am luat in considerare numerele pare
//in marcarea fiecarui multiplu am pornit de la i*i
//am folosit si optimizari pe biti

void pregateste()
{FILE *pin=fopen("ciur.in","r");
fscanf(pin,"%d",&n);
Prime=new char[n/16+10];
memset(Prime,0,sizeof(Prime)*(n/16+1));
fclose(pin);}

void rezolva()
{int i,j;
for(i=3;i<=n;i+=2)
  if(( Prime[i/16] & (1<<(i/2%8)))==0)
    {
    cnt++;
    for(j=i*i;j<=n;j+=i*2)
      Prime[j/16]=Prime[j/16]|(1<<(j/2%8));
    }
}

void incheie()
{delete []Prime;
FILE *pout=fopen("ciur.out","w");
fprintf(pout,"%d",cnt+1);
fclose(pout);}

int main()
{
pregateste();
rezolva();
incheie();
return 0;
}

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.

[•vlad_D]

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

[•k_ounu_eddy]

Ok,ai dreptate,am incercat si merge.
Dar uite ce zice aici http://www.cplusplus.com/reference/clibrary/cstring/memset.html .

void * memset ( void * ptr, int value, size_t num );

Fill block of memory

Sets the first num bytes of the block of memory pointed by ptr to the specified value (interpreted as an unsigned char).

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:

Cod:

#include<iostream>
#include<string.h>
#include<conio.h>
using namespace std;

int main()
{
clrscr();
int *a;
a=new int[1000];
memset(a,0,2);
cout<<a[993];getch();
delete[]a;
return 0;
}

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.

[•Florian]

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. 

[•k_ounu_eddy]

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?

[•alexandru92]

daca puii .......

Cod:

int main()
  {
    int  *p;
    p=new int[1000];
     cout<<p[993]<<endl;
     return 0;

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

[•Prostu]

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:

Cod:

int *p;
p = (int*) malloc( 1000 * sizeof(int) );

sau:

Cod:

int *p;
p = new int[1000];

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:

Cod:

memset(p, 0, 1000 * sizeof(int));

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:

Cod:

int p[1000];

atunci sizeof(p) ar returna valoarea 4000 pe gcc si 2000 pe borland (face diferenta).
Dar aveti grija la urmatorul caz:

Cod:

void f(p[]) {
    // sizeof( p ) aici este valoarea unui pointer adica 2/4/8
}

int main() {
    int p[1000];
    f(p);
}

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.

[•alexandru92]

Imi zice si mie cineva  unde gresesc, adica imi apare KIll By Signel 11 chiar daca phi ii 3 000 001.
Sursa e  aici

[•c_e_manu]

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

[•alexandru92]

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 

[•gabitzish1]

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

[•toni2007]

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.

[•valentinrosca]

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

[•wefgef]

Si atunci de ce iei TLE?

[•SpiderMan]

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

[•JulotM]

Fisier gresit!!!

[•SpiderMan]

Ce inseamna asta ?

[•Sapientia]

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

[•PetcuIoan]

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

[•Sapientia]

Multumesc.

[•AeroH]

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

[•PlayLikeNeverB4]

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

[•andrei8055]

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.