//Autor: Artur Czekalski (Sator)  www.epokaY.net/artur  artur@epokaY.net
//Faktoryzacja 32-bitowych liczb typu unsigned int: od 2^31-1 do 2^31-10001
#include "stdafx.h"
#include <math.h> //sqrt
#include <windows.h> //GetTickCount()
//---------------------------------------------------------------------------
inline void faktor(unsigned int liczba) //szybsze (zwłaszcza dla liczb mających mało podzielników)
{
 if (liczba <= 1) {printf("1");  return;}
 unsigned int w,  pierw = (unsigned int)sqrt((double)liczba);
 int j = 0; //ile razy liczba dzieli się przez i

 //---Najpierw sprawdzam dzielnik 2
 do //dziel liczbę przez 2 tyle razy ile się da
  {w = liczba / 2; //(tu w będzie < liczba)
   if (w * 2 == liczba) {++j;  liczba = w;} //gdy liczba dzieli się przez 2
  }
 while (liczba == w && liczba > 1); //póki się dzieli przez i

 if (j > 0) //ma dzielnik 2
  {printf("2"); //liczba pierwsza
   if (j > 1) printf("^%d", j); //potęga
   if (liczba > 1) printf(" * ");
   else return; //np. dla 16
  }
 //----------------------------------------------
 //---Teraz sprawdzam tylko dzielniki nieparzyste
 unsigned int i;
 for (i=3; i <= pierw; i+=2)
  {j = 0; //ile razy liczba dzieli się przez i
   do //dziel liczbę przez i tyle razy ile się da
    {w = liczba / i; //(tu w będzie < liczba)
     if (w * i == liczba) {++j;  liczba = w;} //gdy liczba dzieli się przez i
    }
   while (liczba == w && liczba > 1); //póki się dzieli przez i

   if (j > 0)
    {printf("%u",i); //liczba pierwsza
     if (j > 1) printf("^%d", j); //potęga
     if (liczba > 1) printf(" * ");
     else break; //np. dla 16
    }
  }
 if (liczba > 1) printf("%u", liczba); //tu największy podzielnik > sqrt(liczba)
}
//===========================================================================
int main(int, char*[])
{
 int i, czas;
 unsigned int L = 4294967295;
 
 czas = GetTickCount();
 for (i=0; i<10000; ++i)
  {printf("\n%u = ", L);  faktor(L);  --L;}
 czas = GetTickCount() - czas;
 
 printf("\nVisual C++ 6.0: Czas=%d", czas);
 //---
 getchar(); return 0;  
}