Vuruqlara ayırma#11611

Vuruqlara ayırma (Həll təhlili)

Çoxlu sayda $1 0^{7}$ 10^7-dən böyük olmayan ədədi faktorizasiya etmək tələb olunduğundan, ilkin hesablama aparmaq sərfəlidir. Modifikasiya edilmiş Eratosfen ələyi vasitəsilə $s p f$ (smallest prime factor) massivini qururuq, burada

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

$n$ ədədinin faktorizasiyası aşağıdakı kimi həyata keçirilir. $n > 1$ n > 1 olduğu müddətcə, cari $n$ qiymətinin ən kiçik sadə böləni olan $p = s p f [n]$ p = spf[n] götürülür və $n$ bu $p$ -yə tam bölünə bildiyi müddətcə dərəcə göstəricisini hesablayaraq bölünür. Sonra $p$ vuruğu müvafiq dərəcədə çıxarılır və növbəti sadə bölənə keçilir. Bu zaman sadə vuruqlar artan qaydada alınır, bu da tələb olunan çıxış formatına uyğundur.

Ələyin qurulması $O (n l o g l o g n)$ O(n~log~log~n) vaxt tələb edir. Hər bölmə əməliyyatı $n$ -i ən azı iki dəfə azaltdığından, bir ədədin faktorizasiyası $O (l o g n)$ O(log~n) vaxtda yerinə yetirilir. $q$ sorğu üçün ümumi vaxt mürəkkəbliyi $O (n l o g l o g n + q l o g n)$ O(n~log~log~n + q~log~n) təşkil edir.

Alqoritmin reallaşdırılması

$s p f [i]$ -də $i$ ədədinin ən kiçik sadə bölənini saxlayan $s p f$ massivini elan edək.

#define MAX 10000001
int spf[MAX + 1];

Sieve funksiyası Eratosfen ələyini reallaşdırır və $s p f$ massivini doldurur.

void Sieve(int n)
{
  for (int i = 0; i < n; i++)
    spf[i] = i;
  for (int i = 2; i <= sqrt(n); i++)
    if (spf[i] == i)
      for (int j = i * i; j < n; j += i)
        if (spf[j] == j) spf[j] = i;
}

C++

factorize funksiyası $s p f$ massivindən istifadə edərək $n$ ədədini sadə vuruqlara ayırır.

void factorize(int n)
{

$n$ ədədi $1$ -dən böyük olduğu müddətcə ondan sadə vuruqları ayırırıq.

  while (n < 1)
  {

$n$ ədədinin ən kiçik sadə böləni $p$ -yə bərabərdir.

    int p = spf[n];

$p^{p o w er}$ p^{power}-in $n$ ədədini böldüyü maksimal $p o w er$ dərəcəsini tapırıq.

    int power = 0;
    while (n % p == 0)
    {
      n /= p;
      power++;
    }

$p^{p o w er}$ p^{power} vuruğunu çap edirik.

    if (power < 1) printf("%d^%d", p, power); else printf("%d", p);

Vuruqlar arasında ' $*$ ' işarəsi çap edilməlidir.

    if (n < 1) printf("*");
  }
  printf("\n");
}

Proqramın əsas hissəsi. Eratosfen ələyindən istifadə edərək $s p f$ massivini doldururuq.

Sieve(MAX);

Hər bir giriş $n$ qiyməti üçün onun sadə vuruqlara ayrılışını çap edirik.

while (scanf("%d", &n) == 1)
  factorize(n);