Funzione di Mertens#3239

Funzione di Mertens (Editoriale)

Implementiamo il setaccio di Möbius in tempo lineare. Con il suo aiuto calcoliamo i valori della funzione di Mertens per tutti i numeri da $1$ a $1 0^{7}$ 10^7.

Implementazione dell'algoritmo

Dichiariamo le costanti e gli array globali.

#define MAX 10000010
#define LMAX 700000
int lp[MAX+1] = {0}, primes[LMAX];
char mu[MAX] = {0};

La funzione LinearEratosfen implementa il setaccio lineare di Eratostene.

Il valore $l p [i]$ contiene il più piccolo divisore primo del numero $i$ .

void LinearEratosfen(void)
{
  int i, j;
  for (i = 2; i <= MAX; ++i) 
  {
    if (lp[i] == 0) 
    {
      lp[i] = i;
      primes[cnt++] = i;
    }
    for (j = 0; j < cnt && primes[j] <= lp[i] &&
                           i * primes[j] <= MAX; j++)
      lp[i * primes[j]] = primes[j];
  }
}

C++

La funzione calc_Mobius calcola la funzione di Möbius, utilizzando l'array $l p$ .

void calc_Mobius(void)
{
  int i, q;
  mu[1] = 1;
  for(i = 2; i < MAX; i++)
  {
    q = i / lp[i];
    if (q % lp[i] != 0) mu[i] = -mu[q];
  }

C++

Utilizziamo l'array $l p$ per memorizzare i valori della funzione di Mertens. Questo permette di non introdurre un ulteriore array lineare e quindi di risparmiare memoria.

  lp[1] = mu[1];
  for(i = 2; i < MAX; i++) lp[i] = lp[i-1] + mu[i];
}

Parte principale del programma. Calcoliamo la funzione di Mertens per tutti i numeri da $1$ a $1 0^{7}$ 10^7.

LinearEratosfen();
calc_Mobius();

Leggiamo i dati di input. Per ogni valore $n$ stampiamo $l p [n]$ .

scanf("%d",&tests);
while(tests--)
{
  scanf("%d",&n);
  printf("%d\n",lp[n]);
}