#!/usr/bin/awk -f
#
# Faktorisierung von Zahlen, Bestimmung der Teiler, des ggT sowie des kgV
#
# 7.7.2006

# Sieb des Eratosthenes anwenden, um die Primzahlen bis zum Wert 'bis' zu
# ermitteln; sie werden in das globale Feld "PZ" eingetragen
function sieb(bis,
              # lokale Variablen
              pz, max_pz, pz2, pz_curr)
{
  # zuerst die 2 hart eintragen, falls 'bis' größer als 1 ist
  if (bis > 1)
  {
    PZ[2] = ""
  }

  # Ausgangsannahme: alle Zahlen sind prim;
  # allerdings reicht die Betrachtung der ungeraden Zahlen aus
  for (pz = 3; pz <= bis; pz += 2)
  {
    PZ[pz] = ""
  }

  # alle Vielfachen einer Primzahl als mögliche Primzahl streichen;
  # Abbruch bei pz mit pz ** 2 > bis
  #
  # mögliche Implementierung:
  #   for (pz = 3; pz ** 2 <= bis; pz += 2)
  max_pz = int(sqrt(bis)) + 1
  for (pz = 3; pz < max_pz; pz += 2)
  {
    # falls Primzahl gefunden
    if (pz in PZ)
    {
      # pz ist Primzahl; nun alle Vielfachen von pz streichen
      #
      # zur Effektivierung streichen wir nur die ungeraden Vielfachen, indem
      # wir immer 2 Mal pz addieren, weil die geraden Vielfachen generell
      # gerade Zahlen sind und somit nicht existieren können, da die einzige
      # gerade Zahl in PZ die 2 ist; und diese wird in der Schleife nicht
      # betrachtet, weil wir erst bei 3 beginnen
      # 
      # wir beginnen die Streichung auch erst bei pz ** 2, weil alle kleineren
      # Vielfachen durch die zuvor betrachteten Primzahlen abgedeckt sind
      # 
      # Beispiel: pz == 7:
      # dann beginnen wir bei 7 * 7 und gehen dann zu 9 * 7, 11 * 7 etc.

      # 2 Mal pz
      pz2 = 2 * pz

      for (pz_curr = pz ** 2; pz_curr <= bis; pz_curr += pz2)
      {
        delete PZ[pz_curr]
      }
    }
  }
}

# Ausgabe der ermittelten Primzahlen
function ausgabe_pz(bis, file,
                    # lokale Variablen
                    i)
{
  for (i = 2; i <= bis; i += (i == 2 ? 1 : 2))
  {
    if (i in PZ)
    {
      printf("%d\n", i) > file
    }
  }
  close(file)
}

# Faktorisierung einer Zahl und Ablage des Ergebnisses im Dictionary FAKTOREN
function faktorisiere(zahl,
                      # lokale Variablen
                      mal_ausgeben, faktoren, orig_zahl, curr_pz, anz_curr_pz, rest)
{
  # Flag, das die Ausgabe eines Mal-Zeichens steuert
  mal_ausgeben = 0
  # Liste der Faktoren leeren
  faktoren = ""
  # Ausgangszahl merken, um später mit der Variablen zahl rechnen zu können
  orig_zahl = zahl

  # wir beginnen bei der Primzahl 2 und klappern aufsteigend alle
  # Primzahlkandidaten ab (das sind die ungeraden Zahlen)
  for (curr_pz = 2; curr_pz <= zahl; curr_pz += (curr_pz == 2 ? 1 : 2))
  {
    if (!(curr_pz in PZ))
    {
      # curr_pz steht nicht in PZ, ist also keine Primzahl
      continue
    }

    # bei jeder aktuellen Primzahl schauen wir, ob diese ein Primfaktor der
    # Ausgangszahl ist, und ermitteln auch, wie oft dies der Fall ist; wir
    # vermerken uns diese Anzahl, die dem Exponenten entspricht
    anz_curr_pz = 0
    while (1)
    {
      rest = zahl % curr_pz
      if (!rest)
      {
        # Rest 0 --> also ist curr_pz Primfaktor; die Anzahl wird
        # inkrementiert, die Zahl selbst durch den Primfaktor geteilt
        anz_curr_pz++
        zahl /= curr_pz
      }
      else
      {
        # rest != 0 --> curr_pz ist kein Primfaktor mehr; demnach Übergang zur
        # nächsten curr_pz
        break
      }
    }

    # wenn anz_curr_pz > 0 und somit curr_pz Primfaktor ist, vermerken wir den
    # Primfaktor curr_pz zusammen mit der Anzahl anz_curr_pz im Feld der
    # faktorisierten Zahlen; wir schreiben dabei Ausdrücke der Form "zahl^exponent"
    if (anz_curr_pz)
    {
      faktoren = faktoren sprintf("%s%d^%d", !faktoren ? "" : "|", curr_pz, anz_curr_pz)
    }
  }

  # die Faktoren nun global im Dictionary vermerken
  FAKTOREN[orig_zahl] = faktoren
}

# Ausgabe der Primfaktorzerlegung einer bestimmten Zahl (der Faktoren-String
# wird übergeben)
function ausgabe_faktoren(faktoren,
                          # lokale Variablen
                          anz, i, j, array, array2, mal_ausgeben)
{
  # die Liste am Trenner "|" in ihre Bestandteile zerlegen
  j = split(faktoren, array, /\|/)

  # über die Bestandteile iterieren
  for (i = 1; i <= j; i++)
  {
    # den aktuellen Bestandteil in Primfaktor und Exponent zerlegen
    split(array[i], array2, /\^/)

    if (mal_ausgeben)
    {
      printf(" * ")
    }

    anz = array2[2]
    if (anz == 1)
    {
      # Primfaktor kommt nur 1 Mal vor
      printf("%d", array2[1])
    }
    else
    {
      # Primfaktor kommt mehr als 1 Mal vor
      printf("%d**%d", array2[1], anz)
    }

    # nach Ausgabe des ersten Primfaktors geben wir ein Malzeichen als
    # Trenner aus
    mal_ausgeben = 1
  }
  printf("\n")
}

# Siebe Primzahlen aus
function siebe_pz()
{  
  # wir berechnen die Primzahlen bis zu max_inp
  printf("Primzahlen aussieben bis: %d\n\n", max_inp)
  # Primzahlen aussieben
  sieb(max_inp)
  # und in das File "pzahlen.txt" ausgeben
  ausgabe_pz(max_inp, "pzahlen.txt")
}

# iterative Implementierung des Euklidischen Algorithmus zur Bestimmung des ggT
# zweier Zahlen
function ggt_iter(a, b,
                  # lokale Variablen
                  tmp)
{
  if (a < 0)
  {
    a = -a
  }
  if (b < 0)
  {
    b = -b
  }
  while (b > 0)
  {
    tmp = a
    a = b
    b = tmp % b
  }
  return a
}

# Bestimmung des kgV zweier Zahlen
#
# das kgV von a und b ist das Produkt der jeweils höchsten Potenz aller
# in a und b enthaltenen Primfaktoren
function kgV(a, b,
             # lokale Variablen
             anz, i, j, zahl, prod, array, array2, KGV, max_pf, fak_str, mal_ausgeben)
{
  # Spezialfall
  if (!a || !b)
  {
    return 0
  }

  # sofern a und b noch nicht faktorisiert sind, dann hier faktorisieren 
  if (!(a in FAKTOREN))
  {
    faktorisiere(a)
  }
  if (!(b in FAKTOREN))
  {
    faktorisiere(b)
  }

  # zuerst übernehmen wir alle Faktoren von a ins kgV
  j = split(FAKTOREN[a], array, /\|/)
  for (i = 1; i <= j; i++)
  {
    split(array[i], array2, /\^/)
    KGV[array2[1]] = array2[2]
  }

  # wir merken uns den größten Primfaktor von a
  max_pf = array2[1]

  # dann tragen wir die Faktoren von b nach
  j = split(FAKTOREN[b], array, /\|/)
  for (i = 1; i <= j; i++)
  {
    split(array[i], array2, /\^/)
    zahl = array2[1]
    anz = array2[2]
    if (zahl in KGV)
    {
      # zahl schon vorhanden, also die maximale Anzahl merken
      if (anz > KGV[zahl])
      {
        KGV[zahl] = anz
      }
    }
    else
    {
      # zahl nicht vorhanden, also einfach nachtragen
      KGV[zahl] = anz
    }
  }

  # max_pf ggf. aktualisieren
  if (zahl > max_pf)
  {
    max_pf = zahl
  }

  # jetzt das kgV ausmultiplizieren und auch als Faktoren-String aufbauen
  prod = 1
  fak_str = ""
  mal_ausgeben = 0
  for (i = 2; i <= max_pf; i += (i == 2 ? 1 : 2))
  {
    if (i in KGV)
    {
      prod *= i ** KGV[i]
      anz = KGV[i]
      fak_str = fak_str sprintf("%s%d%s", mal_ausgeben ? " * " : "",
                                i, anz > 1 ? "**" anz : "")
      mal_ausgeben = 1
    }
  }

  return fak_str ? fak_str " = " prod : prod
}

# Bestimmung des ggT als String
#
# der ggT von a und b ist das Produkt der jeweils niedrigsten Potenz derjenigen
# Primfaktoren, die sowohl in a als auch in b enthalten sind
function ggt_str(a, b,
                 # lokale Variablen
                 anz, i, j, zahl, array, array2, FA, GGT, max_pf, fak_str, mal_ausgeben)
{
  # Spezialfall
  if (a == 1 || b == 1)
  {
    return "1"
  }

  # sofern a und b noch nicht faktorisiert, dann hier faktorisieren 
  if (!(a in FAKTOREN))
  {
    faktorisiere(a)
  }
  if (!(b in FAKTOREN))
  {
    faktorisiere(b)
  }

  # zuerst zerlegen wir den Faktoren-String von a in seine Elemente
  j = split(FAKTOREN[a], array, /\|/)

  # aus den Elementen bauen wir das Dictionary FA auf, dessen Keys die
  # Primfaktoren und dessen Werte die Exponenten sind
  for (i = 1; i <= j; i++)
  {
    split(array[i], array2, /\^/)
    FA[array2[1]] = array2[2]
  }

  # jetzt zerlegen wir den Faktoren-String von b in seine Elemente
  j = split(FAKTOREN[b], array, /\|/)

  # die Elemente werden der Reihe nach durchlaufen
  for (i = 1; i <= j; i++)
  {
    # Element in Primfaktor und Exponent zerlegen
    split(array[i], array2, /\^/)
    zahl = array2[1]
    anz = array2[2]
    if (zahl in FA)
    {
      # der Primfaktor "zahl" kommt auch in FA vor, ist also in den GGT zu
      # übernehmen, und zwar mit der minimalen Anzahl
      anza = FA[zahl]
      GGT[zahl] = (anz < anza) ? anz : anza
      # wir merken uns gleich noch den größten Primfaktor des GGT
      max_pf = zahl
    }
  }

  # jetzt den Faktoren-String aufbauen
  fak_str = ""
  mal_ausgeben = 0
  for (i = 2; i <= max_pf; i += (i == 2 ? 1 : 2))
  {
    if (i in GGT)
    {
      anz = GGT[i]
      fak_str = fak_str sprintf("%s%d%s", mal_ausgeben ? " * " : "",
                                i, anz > 1 ? "**" anz : "")
      mal_ausgeben = 1
    }
  }

  # neben dem Faktoren-String geben wir den iterativ berechneten ggT zurück
  return fak_str ? fak_str " = " ggt_iter(a, b) : ggt_iter(a, b)
}

BEGIN {
  # zuerst schauen wir, was unser Programm machen soll:
  # Option -f  --> faktorisieren
  # Option -t  --> Teiler bestimmen
  # Option -g  --> ggT
  # Option -k  --> kgV

  # Achtung:
  # die Options-Argumente sind aus ARGV zu streichen, damit sie von AWK nicht
  # als die Namen von Eingabe-Dateien interpretiert werden
  for (i = 1; i < ARGC; i++)
  {
    if (ARGV[i] == "-f")
    {
      func_f = 1 ; ARGV[i] = ""
    }
    else if (ARGV[i] == "-t")
    {
      func_t = 1 ; ARGV[i] = ""
    }
    else if (ARGV[i] == "-g")
    {
      func_g = 1 ; ARGV[i] = ""
    }
    else if (ARGV[i] == "-k")
    {
      func_k = 1 ; ARGV[i] = ""
    }
  }

  # wir lesen alle zu bearbeitenden Zahlen ein; negative Zahlen werden mit
  # -1 multipliziert; außerdem werden alle Eingaben auf gannzahlige Werte
  # gerundet
  inp_idx = 0
  while (1)
  {
    if ((getline var) <= 0)
    {
      # EOF erreicht
      break
    }

    if (var < 1)
    {
      var = -var
    }

    # auf gannzahligen Wert runden
    var = sprintf("%d", var) + 0

    if (!inp_idx || (var > max_inp))
    {
      # maximalen Eingabe-Wert merken
      max_inp = var
    }

    # neu gelesenen Wert in ein Feld eintragen
    input[inp_idx++] = var
  }

  # für Faktorisierung und kgV benötigen wir Primzahlen; diese sieben wir daher hier
  # aus
  if (func_f || func_k)
  {
    siebe_pz()
  }

  if (func_f || func_t)
  {
    # bei Faktorisierung und Teilerbestimmung gehen wir schrittweise durch die
    # Zahlen und geben die Primfaktorzerlegung sowie die Teiler aus
    for (i = 0; i < inp_idx; i++)
    {
      zahl = input[i]

      if (func_f)
      {
        # Faktorisierung

        printf("%d = ", zahl)
        if (zahl in PZ)
        {
          # eine Primzahl geben wir unverändert aus, da sie ihr einziger
          # Primfaktor ist
          printf("%d\n", zahl)
        }
        else
        {
          # eine Nicht-Primzahl wird faktorisiert
          faktorisiere(zahl)
          ausgabe_faktoren(FAKTOREN[zahl])
        }
      } 

      if (func_t)
      {
        # Teilerbestimmung

        printf("T%d = { ", zahl)
        for (teiler = 1; teiler <= zahl; teiler++)
        {
          # schrittweise Teilerermittlung durch Modulo-Division
          if (!(zahl % teiler))
          {
            # wir wissen, daß die 1 und zahl selbst Teiler sind, behandeln sie
            # aber ganz normal in der Schleife mit, auch wenn dadurch 2
            # Modulo-Divisionen umsonst ablaufen; ab dem 2. Teiler schreiben
            # wir vor der Zahl ", " als Trenner aus
            printf("%s%d", (teiler == 1) ? "" : ", ", teiler)
          }
        }

        print " }"
      }

      print ""
    }
  }

  if (func_g)
  {
    # ggT bestimmen

    # wir bilden den ggT aller Zahlenpaare
    for (i = 1; i < inp_idx; i += 2)
    {
      a = input[i-1]
      b = input[i]
      if (a && b)
      {
        # a und b ungleich Null --> ggT berechnen
        printf("ggT(%d, %d) = %s\n", a, b, ggt_str(a, b))
      }
      else
      {
        # a und b gleich Null --> ggT ist unendlich
        printf("ggT(%d, %d) = unendlich\n", a, b)
      }
    }

    print ""
  }

  if (func_k)
  {
    # kgV bestimmen

    # wir bilden den kgV aller Zahlenpaare
    for (i = 1; i < inp_idx; i += 2)
    {
      a = input[i-1]
      b = input[i]
      printf("kgV(%d, %d) = %s\n", a, b, kgV(a, b))
    }
  }
}