Функція Мертенса#3239

Функція Мертенса (Розбір)

Реалізуємо решето Мебіуса за лінійний час. З його допомогою обчислимо значення функції Мертенса для всіх чисел від $1$ до $1 0^{7}$ 10^7.

Реалізація алгоритму

Оголосимо константи та глобальні масиви.

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

Функція LinearEratosfen реалізує лінійне решето Ератосфена.

Значення $l p [i]$ містить найменший простий дільник числа $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++

Функція calc_Mobius обчислює функцію Мебіуса, використовуючи масив $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++

Використовуємо масив $l p$ для зберігання значень функції Мертенса. Це дозволяє не вводити додатковий лінійний масив і тим самим економить пам'ять.

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

Основна частина програми. Обчислюємо функцію Мертенса для всіх чисел від $1$ до $1 0^{7}$ 10^7.

LinearEratosfen();
calc_Mobius();

Читаємо вхідні дані. Для кожного значення $n$ виводимо $l p [n]$ .

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