Mertens funksiyası#3239

Mertens funksiyası (Həll təhlili)

Mebius ələyini xətti vaxt ərzində realizə edək. Onun köməyilə $1$ -dən $1 0^{7}$ 10^7-ə qədər bütün ədədlər üçün Mertens funksiyasının qiymətlərini hesablayaq.

Alqoritmin realizasiyası

Sabitləri və qlobal massivləri elan edək.

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

LinearEratosfen funksiyası Eratosfen xətti ələyini realizə edir.

$l p [i]$ qiyməti $i$ ədədinin ən kiçik sadə bölənini saxlayır.

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 funksiyası $l p$ massivindən istifadə edərək Mebius funksiyasını hesablayır.

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

Mertens funksiyasının qiymətlərini saxlamaq üçün $l p$ massivindən istifadə edirik. Bu, əlavə xətti massiv daxil etməməyə imkan verir və bununla da yaddaşa qənaət edir.

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

Proqramın əsas hissəsi. $1$ -dən $1 0^{7}$ 10^7-ə qədər bütün ədədlər üçün Mertens funksiyasını hesablayırıq.

LinearEratosfen();
calc_Mobius();

Giriş məlumatlarını oxuyuruq. Hər bir $n$ qiyməti üçün $l p [n]$ çap edirik.

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