#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main()
{
   unsigned int iEingabe = 1, iIntsize, i, j, k, iModIntsize;   //Deklaration und einmalige Festlegung von Konstanten
   iIntsize=sizeof(int)*8;
   iModIntsize = iIntsize-1;
   
   while (0 < iEingabe)                                         //Berechnungsschleife solange bis 0 eingegeben wird
   {  
      printf ("Bitte geben sie eine Zahl ein, die sie faktorisieren moechten (exit = 0):\n"); //Eingabe Zahl
      scanf ("%i",&iEingabe);
      printf ("Primfaktorzerlegung: 1 ");
                                             
      k = iEingabe/iIntsize+1;                                  //Siebgröße bestimmen
      unsigned int sieb[k];
      for (j=0; j<k; sieb[j++]=0);                              //Sieb löschen
      k=0; i=2;                                                 //Laufvariablen initialisieren

      while (1 < iEingabe)                                      //Abbruchbedingung Zahl = 1
      {  
         if (0 == (sieb[i/iIntsize]&1<<(i&iModIntsize)))        //Laufvariable = Primzahl?
         {
               while (0 == iEingabe%i)                          //Wenn Eingabe durch Laufvariable teilbar...
               {    
                   iEingabe/=i;                                 //...dann so oft teilen wie möglich, Anzahl der Teilungen merken
                   k++;                                         //increment k :>
               }
               
               if (0 < k)                                       //Anzahl der Teilungen > 0, dann Ausgabe des Teilers und Anzahl Teilungen
               {
                   printf("* %i^%i ",i,k);
                   k=0;
               }

               j=2*i;                                           //Primzahlensieb aufbauen, für obige Primzahlenerkennung
               while (j < sqrt(iEingabe))
               {
                   sieb[j/iIntsize]|=1<<(j&iModIntsize);
                   j+=i;
               }      
         }
         i++;
      }
      printf("\n\n");
   }
}