Mertens function#3239

Mertens function (Editorial)

Let’s implement the Möbius sieve in linear time. Using it, we compute the values of the Mertens function for all numbers from $1$ to $1 0^{7}$ 10^7.

Algorithm implementation

Declare the constants and global arrays.

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

The LinearEratosfen function implements the linear sieve of Eratosthenes.

The value $l p [i]$ contains the smallest prime divisor of the number $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++

The calc_Mobius function computes the Möbius function using the $l p$ array.

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

Use the $l p$ array to store the values of the Mertens function. This allows us to avoid introducing an additional linear array and therefore saves memory.

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

The main part of the program. Compute the values of the Mertens function for all numbers from $1$ to $1 0^{7}$ 10^7.

LinearEratosfen();
calc_Mobius();

Read the input data. For each value of $n$ print $l p [n]$ .

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