Calcularea functiei phi(N) folosind Ciurul lui Eratostene

[•wefgef]

Vom folosi un vector phi[], unde phi[ x ] va reprezenta numarul de numere prime cu x, mai mici decat x. Initializam phi[ x ] cu x-1. Apoi parcurgem numerele de la 2 la N, si pentru un numar fixat x, vom scadea din fiecare multiplu de-ai sai phi[ x ].

Cod:

for (int i = 1; i <= N; ++i)
    phi[i] = i-1;
for (int i = 2; i <= N; ++i)
    for (int j = 2*i; j <= N; j += i)
        phi[j] -= phi[i];

Puteti folosi acest cod pentru a rezolva problemele Fractii si Sum.

Am decis sa fac un topic separat deoarece este foarte util acest algoritm si apare in multe alte probleme.

[•Dastas]

Super, eu am facut problema fractii mult mai urat. Tin minte ca generam numere prime si apoi foloseam doua formule. Nu m-am gandit sa fac scazand din multiplii...

Mersi mult, foarte folositor!

[•pauldb]

Merge si asa:

Cod:

for (int i=1;i<=N;i++) phi[i]=i;

for (int i=2;i<=N;i++)
   if (phi[i]==i)
      for (j=i;j<=N;j+=i) phi[j] /=i, phi[j] *= (i-1);

In principiu, cred ca ar trebui sa mearga mai repede, pentru se merge mai departe doar din numerele prime. Practic, aici apar inmultiri si impartiri care merg mai incet. Nu stiu daca se face diferenta, dar poate ajuta pe cineva.

[•bogdan88]

Paul am scris cu ai explicat tu...dar nu da rezultatul corect. poate ai gresit ceva si eu nu imi dau seama

[•pauldb]

Gata, am corectat.

[•sandyxp]

0.4 sec pe 1 milion vs 1 sec
"ciurul" lui pauldb bate

[•Szabi]

Salut! poate vi se pare o prostie intrebarea mea, dar am o nelamurire... inteleg despre ce e vorba in ciurul lui Erathosthenes si inteleg si indicatorul lui Euler, dar nu inteleg unde se intalnesc cele doua notiuni, adica de unde iese algoritmul descris aici. am  folosit deja algoritmul la niste probleme si vad ca functioneaza,dar nu inteleg cum... ma poate lamuri cineva? multumesc anticipat 

[•Mishu91]

Tu nu folosești efectiv Ciurul, ci doar principiul, adică la început atribui fiecărui număr phi(i) = i-1, 1<=i<=N, iar apoi fac ca la ciur, fiecărui număr ii parcurg toți multipli și scad din phi(j) phi(i), unde j este multiplu al lui i. De ce? Pentru că astfel scad toate numerele care nu sunt relativ prime la j.

[•SpiderMan]

Imi puteti spune exact ce trebuie sa fac dupa ce am calculat phi de fiecare numar? si explicatia pentru care ati facut phi[j]=phi[j]-phi[ i] ? Merci
EDIT: M-am prins. Deci de exemplu pentru numarul 6 stim ca are 2 numere prime cu el: si anume 1 si 5. Acum daca numarul N e 7, numarul 6 mai e prim si cu 7. Cum fac mai incolo?Adica nu inteleg de ce fac nr*2+1, unde nr e suma phi-urilor

[•pauldb]

4 nu e prim cu 6. Numerele prime cu 6 mai mici ca el sunt 1 si 5. Iti recomand sa te mai pui la punct cu notiunile matematice elementare (divizibilitate, numar prim, cmmdc, etc.). Nu se poate face informatica fara sa le stapanesti si, din ce am citit scris de tine pe forum, nu e prima ta greseala catastrofala. Presupun ca esti intr-o clasa destul de mica si nu trebuie sa te simti descurajat, de aceea incerc sa te sfatuiesc spre binele tau.

Phi(i) = numarul de numere prime cu i mai mici ca i. Tu poti avea i atat la numitor, cat si la numarator, deci de acolo apare 2*phi(i), pentru orice i. Si mai trebuie sa numeri si fractia 1/1.

[•SpiderMan]

4 nu e prim cu 6. Numerele prime cu 6 mai mici ca el sunt 1 si 5. Iti recomand sa te mai pui la punct cu notiunile matematice elementare (divizibilitate, numar prim, cmmdc, etc.). Nu se poate face informatica fara sa le stapanesti si, din ce am citit scris de tine pe forum, nu e prima ta greseala catastrofala. Presupun ca esti intr-o clasa destul de mica si nu trebuie sa te simti descurajat, de aceea incerc sa te sfatuiesc spre binele tau.

Phi(i) = numarul de numere prime cu i mai mici ca i. Tu poti avea i atat la numitor, cat si la numarator, deci de acolo apare 2*phi(i), pentru orice i. Si mai trebuie sa numeri si fractia 1/1.

Scuze am scris gresit 4 in loc de 1 am fost grabit si am scris gresit scuze, si am inceput informatica de anul asta, clasa a 9-a si merci acum am inteles DE CE era 2* ala ca 1 stiam ca e 1/1 .

[•mihai.plesa]

Merge si asa:

Cod:

for (int i=1;i<=N;i++) phi[i]=i;

for (int i=2;i<=N;i++)
   if (phi[i]==i)
      for (j=i;j<=N;j+=i) phi[j] /=i, phi[j] *= (i-1);

In principiu, cred ca ar trebui sa mearga mai repede, pentru se merge mai departe doar din numerele prime. Practic, aici apar inmultiri si impartiri care merg mai incet. Nu stiu daca se face diferenta, dar poate ajuta pe cineva.

de ce phi[j] /=i ?
de ce phi[j] *=(i-1) ?
Multumesc!

[•PlayLikeNeverB4]

phi[j] := phi[j] - phi[j]/i = phi[j] * ( 1 - 1/i ) = phi[j] * (i-1)/i

Pentru explicatii exista intotdeauna Google

[•popoiu.george]

Vom folosi un vector phi[], unde phi[ x ] va reprezenta numarul de numere prime cu x, mai mici decat x. Initializam phi[ x ] cu x-1. Apoi parcurgem numerele de la 2 la N, si pentru un numar fixat x, vom scadea din fiecare multiplu de-ai sai phi[ x ].

Cod:

for (int i = 1; i <= N; ++i)
    phi = i-1;
for (int i = 2; i <= N; ++i)
    for (int j = 2*i; j <= N; j += i)
        phi[j] -= phi;


Puteti folosi acest cod pentru a rezolva problemele Fractii si Sum.

Am decis sa fac un topic separat deoarece este foarte util acest algoritm si apare in multe alte probleme.

E O(N) ?

[•SebiSebi]

Nu chiar. E O(N log log N). 

[•klamathix]

E O(nlogn) de fapt.

[•SebiSebi]

Da, scuze. O(N log log N) e pentru Ciurul lui Erastotene, dar acolo se sare peste numerele care nu sunt prime.

[•fdproxy]

Pe multe procesoare moderne varianta de mai jos este mai rapida decat varianta originala.

Cod:

   // N divizibil cu 4, de exemplu
    for ( int i = 1; i <= N; i+=4 )
    {
      phi[i] = i - 1;
      phi[i+1] = i;
      phi[i+2] = i + 1;
      phi[i+3] = i + 2;
    }

    // sau

    for ( int i = 0; i < N; i+=4 )
    {
      phi[i+1] = i;
      phi[i+2] = i + 1;
      phi[i+3] = i + 2;
      phi[i+4] = i + 3;
    }

[•wefgef]

Din punctul meu de vedere astfel de artificii ar trebui descurajate, cu exceptia catorva ramuri obscure ale industriei.

[•emanuel_r]

Un aricol folositor in acest sens puteti gasi la adresa:

https://www.whitman.edu/mathematics/higher_math_online/section03.09.html