Riyaziyyat dərsi (Həll təhlili)

Məsələdə $n$ ədədini sadə vuruqlara ayırmaq tələb olunur, yəni onu n = p_1^{a_1} \cdot p_2^{a_2} \cdot ... \cdot p_k^{a_k} şəklində təqdim etmək lazımdır, burada p_1 < p_2 < ... < p_k — sadə ədədlərdir. Hər bir sadə bölən p_i öz dərəcəsi a_i ilə birlikdə çıxarılır, əgər a_i > 1 olarsa.

Mümkün bölənləri $i$ artan sırada, $2$-dən başlayaraq nəzərdən keçirəcəyik. Əgər $i$ $n$-i bölürsə, onda $n$-i $i$-yə bölmə tam alınana qədər bölürük və bölmələrin sayını $c$-də hesablayırıq. Alınan $c$ qiyməti məhz o dərəcədir ki, $i$ bu dərəcə ilə ayrılışa daxil olur. Bundan sonra $i$-ni çıxarırıq, əgər c = 1 olarsa, və ya i^c-ni çıxarırıq, əgər c > 1 olarsa.

Bölənlərin yoxlanılmasını \sqrt{n}-ə qədər aparmaq kifayətdir. Əgər ədədin $2$-dən \sqrt{n}-ə qədər olan aralıqda bölənləri yoxdursa, onda bu ədəd sadədir. Buna görə də dövr başa çatdıqdan sonra cari $n$ qiyməti ya $1$-ə bərabərdir, ya da sadə ədəddir — ayrılışın son vuruğudur, onu da çıxarmaq lazımdır. Belə "böyük" vuruq yalnız bir dənə ola bilər: \sqrt{n}-dən böyük olan iki vuruğun hasili $n$-dən çox olar.

Misal. n = 3240 ədədinə baxaq.

• i = 2: 3240 \to 1620 \to 810 \to 405, c = 3. 2^3* çıxarırıq, çünki n = 405 > 1.

• i = 3: 405 \to 135 \to 45 \to 15 \to 5, c = 4. 3^4* çıxarırıq, çünki n = 5 > 1.

• i = 4: 4 \cdot 4 > 5, dövr başa çatır.

Qalıq n = 5 > 1 sadə vuruqdur, $5$ çıxarırıq.

Cavab: 2^3*3^4*5.

Alqoritmin realizasiyası

factor funksiyası $n$ ədədinin sadə vuruqlara ayrılışını həyata keçirir.

void factor(int n)
{
  for (int i = 2; i <= sqrt(n); i++)
  {
    if (n % i) continue;

$i$ ədədi $n$-in bölənidir. $c$ dəyişənində onun $n$-in ayrılışına daxil olduğu dərəcəni hesablayırıq.

    int c = 0;
    while (n % i == 0) n /= i, c++;

i^c vuruğunu çıxarırıq. Əgər vuruğun dərəcəsi c = 1 olarsa, yalnız $i$-ni çıxarırıq. Əks halda, $i$ vuruğunu onun dərəcəsi ilə birlikdə çıxarırıq.

    if (c > 1) printf("%d^%d",i,c); else printf("%d",i);

Əgər $n$ ədədi hələ tam ayrılmayıbsa (n > 1), vurma işarəsini çıxarırıq.

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

Əgər dövr başa çatdıqdan sonra $n$ qiyməti $1$-dən böyükdürsə, onda o sadədir.

  if (n > 1) printf("%d",n);
  printf("\n");
}

Proqramın əsas hissəsi. Giriş ədədi $n$-i oxuyuruq və onun faktorizasiyasını işə salırıq.

scanf("%d",&n);
factor(n);

Python realizasiyası

import math

factor funksiyası $n$ ədədinin sadə vuruqlara ayrılışını həyata keçirir.

def factor(n):
  for i in range(2, math.isqrt(n) + 1):
    if n % i: continue

$i$ ədədi $n$-in bölənidir. $c$ dəyişənində onun $n$-in ayrılışına daxil olduğu dərəcəni hesablayırıq.

    c = 0
    while n % i == 0:
      n //= i
      c += 1

i^c vuruğunu çıxarırıq. Əgər vuruğun dərəcəsi c = 1 olarsa, yalnız $i$-ni çıxarırıq. Əks halda, $i$ vuruğunu onun dərəcəsi ilə birlikdə çıxarırıq.

    if c > 1: print(i,"^",c, sep = "", end="")
    else: print(i, end="")

Əgər $n$ ədədi hələ tam ayrılmayıbsa (n > 1), vurma işarəsini çıxarırıq.

    if n > 1: print("*", end="")

Əgər dövr başa çatdıqdan sonra $n$ qiyməti $1$-dən böyükdürsə, onda o sadədir.

  if n > 1: print(n)
  else: print()

Proqramın əsas hissəsi. Giriş ədədi $n$-i oxuyuruq və onun faktorizasiyasını işə salırıq.

n = int(input())
factor(n)