Eratostene și alte ciururi

Ciurul lui Eratostene este o metodă rapidă prin care stabilește despre fiecare număr natural mai mic sau egal cu un n dat dat este prim sau nu. Valoarea lui n trebuie să fie suficient de mică pentru a putea declara un tablou P cu n+1 elemente, un element P[k] având valoarea 1 dacă k este prim, respectiv valoarea 0 dacă k nu este prim.

Următoarea secvență C++ construiește tabloul P[]:

int P[n+1];
for(int i = 0 ; i <= n ; i ++)
    P[i] = 1;
P[0] = P[1] = 0;
for(int i = 2 ; i * i <= n ; i ++)
    if(P[i] == 1)
        for(int j = 2 ; i * j <= n ; j ++)
            P[i * j] = 0;

Ideea de mai sus poate fi utilizată pentru a determina diverse rezultate în care intervin divizorii unui număr, rezultate calculate pentru toate numerele mai mici sau egale cu n:

• numărul de divizori
• suma divizorilor
• cel mai mic divizor prim
• cel mai mare divizor prim
• indicatorul lui Euler

Numărul de divizori

• construim un vector Nr[]. La final, Nr[x] va fi numărul de divizori ai lui x;
• inițializăm elementele vectorului Nr[] cu 0;
• parcurgem vectorul și pentru fiecare element Nr[i] mărim valorile elementelor Nr[k], unde k = i * j este multiplu al lui i – dacă i este divizor al lui k, atunci trebuie numărat ca atare.

int Nr[DIM + 1];
for(int i = 1 ; i <= DIM ; i ++)
    Nr[i] = 0;
for(int i = 1; i <= DIM ; i ++)
    for(int j = 1 ; i * j <= DIM ; j ++)
        Nr[i * j] ++;

OBS: Un număr x este prim dacă și numai dacă la final Nr[x] este egal cu 2.

Suma divizorilor

• construim un vector S[]. La final, S[x] va reprezenta suma divizorilor lui x;
• inițializăm elementele vectorului S[] cu 0;
• parcurgem vectorul și pentru fiecare element S[i] mărim valorile elementelor S[k] cu i, unde k = i * j este multiplu al lui i – dacă i este divizor al lui k, atunci trebuie adunat la suma divizorilor lui k.

int S[DIM + 1];
for(int i = 1 ; i <= DIM ; i ++)
    S[i] = 0;
for(int i = 1; i <= DIM ; i ++)
    for(int j = 1 ; i * j <= DIM ; j ++)
        S[i * j] += i;

OBS: Un număr x este prim dacă și numai dacă la final S[x] este egal cu x+1.

Cel mai mic/mare divizor prim

• construim un vector M[]. La final, M[x] va reprezenta cel mai mic divizor (factor) prim al lui x;
• inițializăm elementele vectorului M[x] cu x – pentru numerele prime cel mai mic factor prim sunt ele însele;
• parcurgem numerele începând de la 2 și pentru fiecare număr i prim (pentru care M[i] = i) modificăm, dacă este cazul, cel mai mic factor prim pentru toți multipli k = i * j lui i.

int M[DIM + 1];
for(int i = 1 ; i <= DIM ; i ++)
    M[i] = i;
for(int i = 2; i <= DIM ; i ++)
    if(M[i] == i)
        for(int j = 2 ; i * j <= DIM ; j ++)
            if(M[i * j] == i * j)
                M[i * j] = i;

OBS:

• Un număr x este prim dacă și numai dacă la final M[x] este egal cu x.
• La parcurgerea multiplilor lui i, vom modifica multiplul k = i * j numai dacă M[k] este încă k. De exemplu, pentru i=3, nu-l mai modifică pe M[6] – a fost deja modificat pentru i=2.
• Dacă modificăm M[k] de pentru fiecare i, deoarece i este considerat în ordine crescătoare, la final M[k] va memora cel mai mare divizor prim al lui k. Următoarea secvență obține acest rezultat – observați că modificările sunt minore:

int M[DIM + 1];
for(int i = 1 ; i <= DIM ; i ++)
    M[i] = i;
for(int i = 2; i <= DIM ; i ++)
    if(M[i] == i)
        for(int j = 2 ; i * j <= DIM ; j ++)
            M[i * j] = i;

Indicatorul lui Euler

Indicatorul lui Euler este tratat în acest articol. Reluăm aici numai secvența C/C++:

int F[DIM + 1];
for(int i =1 ; i <= DIM ; i ++)
    F[i] = i;
for(int i = 2;  i <= DIM ; i ++)
    if(F[i] == i)
    {
        for(int j = 1 ; j * i <= DIM ; j ++)
            F[j * i]= F[j * i] / i * (i - 1);
    }

OBS: Un număr x este prim dacă și numai dacă la final F[x] este egal cu x-1.

Alte probleme

Încercați să determinați în același mod:

• numărul factorilor primi
• suma/produsul factorilor primi
• etc.