/********************************************
*    Factorization of an integer number     *
* ----------------------------------------- *
* Sample run:                               *
*                                           *
* ? 394616                                  *
*                                           *
* 2 2 2 107 461                             *
*                                           *
* ----------------------------------------- *
* Ref.: "Mathématiques par l'informatique   *
*        individuelle (1) par H. Lehning    *
*        et D. Jakubowicz, Masson, Paris,   *
*        1982" [BIBLI 06].                  *
*                                           *
*               C++ version by J-P Moreau.  *
*                    (www.jpmoreau.fr)      *
********************************************/
#include <stdio.h>
#include <math.h>

// Labels: e50,e100,e150,e200

double d,eps,m,n,i;


void main() {
  eps=1e-6;
  // Enter integer number to be factorized
  printf("\n");
  printf(" ? "); scanf("%lf",&n);
  printf("\n");
  printf(" ");
  // Test if multiple of 2
e50:d=n-2*int(n/2);
    if (fabs(d)<eps) {printf("2 "); n=n/2; goto e50;}
  // Test if multiple of 3
e100:d=n-3*int(n/3);
    if (fabs(d)<eps) {printf("3 "); n=n/3; goto e100;}
  // Test of divisors 6i-1 and 6i+1 up to sqrt(n)
  // Prime numbers are of the form 6i-1 or 6i+1
  m=floor(sqrt(n))+1;
  i=6;
  while (i<m+1) {
e150:d=n-(i-1)*int(n/(i-1));
    if (fabs(d)<eps) {printf("%4.0f ",i-1); n=n/(i-1); goto e150;}
e200:d=n-(i+1)*int(n/(i+1));
    if (fabs(d)<eps) {printf("%4.0f ",i+1); n=n/(i+1); goto e200;}
    i=i+6;
  }
  if (n>1) printf("%4.0f\n\n",n);
  else printf("\n\n");
}

// end of file factors.cpp