//Autor: Artur Czekalski (Sator)  www.epokaY.net/artur  artur@epokaY.net
//faktoryzacja liczb int64
#include "stdafx.h"
#include <stdlib.h> //_i64toa
#include <math.h> //sqrt
#include <windows.h> //GetTickCount()

char gBufor[64];
//---------------------------------------------------------------------------
void faktor(__int64 liczba)
{
 if (liczba <= 1i64) {printf("1");  return;}
 __int64 w, pierw = (__int64)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 / 2i64; //(tu w będzie < liczba)
   if (w * 2i64 == liczba) {++j;  liczba = w;} //gdy liczba dzieli się przez 2
  }
 while (liczba == w && liczba > 1i64); //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 > 1i64) printf(" * ");
   else return; //np. dla 16
  }

 //---Teraz sprawdzam tylko dzielniki nieparzyste
 __int64 i;
 for (i=3i64; i <= pierw; i+=2i64)
  {
   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 > 1i64); //póki się dzieli przez i

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