Çarpanlara Ayırma#11611

Çarpanlara Ayırma (Editoryal)

$1 0^{7}$ 10^7'yi aşmayan çok sayıda sayıyı çarpanlarına ayırmak gerektiğinden, bir ön hesaplama yapmak avantajlıdır. Değiştirilmiş Eratosthenes eleği yardımıyla, $s p f$ (smallest prime factor - en küçük asal çarpan) dizisini oluşturacağız; burada

$s p f [i]$ , $i$ sayısının en küçük asal çarpanını içerir

$n$ sayısının çarpanlarına ayrılması şu şekilde gerçekleştirilir. $n > 1$ n > 1 olduğu sürece, $n$ 'nin şu anki değerinin en küçük asal çarpanı olan $p = s p f [n]$ p = spf[n]'yi alıyoruz ve bölme tam olarak gerçekleştiği sürece $n$ 'yi $p$ 'ye bölüp üssü sayıyoruz. Ardından $p$ çarpanını ilgili üssüyle birlikte yazdırıyoruz ve bir sonraki asal çarpana geçiyoruz. Bu durumda asal çarpanlar artan sırada elde edilir, bu da gerekli çıktı biçimine karşılık gelir.

Eleğin oluşturulması $O (n l o g l o g n)$ O(n~log~log~n) zaman gerektirir. Her bölme işlemi $n$ 'yi en az yarıya indirdiğinden, bir sayının çarpanlarına ayrılması $O (l o g n)$ O(log~n) sürede gerçekleştirilir. $q$ sorgu için toplam zaman karmaşıklığı $O (n l o g l o g n + q l o g n)$ O(n~log~log~n + q~log~n) olur.

Algoritmanın Gerçekleştirilmesi

$s p f [i]$ 'nin $i$ sayısının en küçük asal çarpanını içerdiği $s p f$ dizisini tanımlayalım.

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

Sieve fonksiyonu Eratosthenes eleğini gerçekleştirir ve $s p f$ dizisini 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 fonksiyonu, $s p f$ dizisini kullanarak $n$ sayısını asal çarpanlarına ayırır.

void factorize(int n)
{

$n$ sayısı $1$ 'den büyük olduğu sürece asal çarpanları ayıklıyoruz.

  while (n > 1)
  {

$n$ sayısının en küçük asal çarpanı $p$ 'ye eşittir.

    int p = spf[n];

$p^{p o w er}$ p^{power}'nin $n$ sayısını böldüğü maksimum $p o w er$ üssünü buluyoruz.

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

$p^{p o w er}$ p^{power} çarpanını yazdırıyoruz.

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

Çarpanlar arasında ' $*$ ' işareti yazdırılmalıdır.

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

Programın ana bölümü. Eratosthenes eleğini kullanarak $s p f$ dizisini dolduruyoruz.

Sieve(MAX);

Her giriş değeri $n$ için, onun asal çarpanlara ayrılmış halini yazdırıyoruz.

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