/*
  Questo programma fa parte di una libreria messa a disposizione dei
  lettori del libro
  Alessandro Languasco & Alessandro Zaccagnini,
  Introduzione alla Crittografia, Ulrico Hoepli Editore, Milano, 2004.

  Scomposizione in fattori primi dell'intero "n": divisione per
  tentativi.
  Si veda il Paragrafo 6.5.1 del libro citato.
*/

#include <iostream>
#include <cmath>
#include <vector>
#include "aritmetica.cc"

/*
  Variabile per il conteggio del numero di iterazioni necessarie
  (serve per confrontare fra loro i vari algoritmi proposti)
*/
long long int
iterazioni;

/*
  Se l'intero "n" è divisibile per l'intero "m", restituisci
  l'esponente "k" per cui esiste un intero "a" tale che "n = m^k * a",
  dove "a" non è divisibile per "n". All'uscita della funzione, "n"
  vale "a".
*/
long long unsigned
prova_il_fattore(long long int& n, const long long int m) {

  ++iterazioni;
  unsigned k = 0;
  while (n % m == 0) {
    ++k;
    n /= m;
  }
  return k;
}

/*
  Prova a dividere "n" per tentativi fino ad "m".
  Stampa gli eventuali fattori primi trovati con i loro esponenti
  (memorizzandoli nei vettori "basi" ed "esponenti" rispettivamente).
  Restituisci la parte di "n" eventualmente non fattorizzata.
*/
long long int
dividi_per_tentativi(long long int nn, long long int m,
		     std::vector<long long int>& basi,
		     std::vector<int>& esponenti) {

  long long int n = nn;
  if (n < 0)
    n *= -1;
  // Se "n" è pari, rimuovi la giusta potenza di 2
  int k = prova_il_fattore(n, 2);
  if (k > 0) {
    basi.push_back(2);
    esponenti.push_back(k);
    std::cout << " 2 ";
    if (k > 1)
      std::cout << "^ " << k;
    std::cout << "* ";
  }
  // Verifica l'eventuale divisibilità di "n" per i primi dispari
  // "piccoli", cioè minori di "m"
  for (long long int i = 3; i <= m; i += 2) {
    k = prova_il_fattore(n, i);
    if (k > 0) {
      basi.push_back(i);
      esponenti.push_back(k);
      std::cout << i;
      if (k > 1)
	std::cout << "^ " << k;
      std::cout << " * ";
    }
    // Se "i" è grande, esci dal ciclo
    if (i * i > n)
      i = m;
  }
  return(n);
}

int
main() {
  long long int n, m;
  std::vector<long long int> basi;
  std::vector<int> esponenti;

  // Come numero di prova usiamo il "numero di Jevons" definito a p. 175
  n = 8616460799LL;

  std::cout << "Fattorizzazione per tentativi di " << n << " = ";
  long long unsigned rq = radice_quadrata(n);
  m = dividi_per_tentativi(n, rq, basi, esponenti);
  std::cout << m << std::endl;
  std::cout << "Sono state necessarie " << iterazioni << " iterazioni";
  std::cout << std::endl;

  // Un altro intero di prova
  n = 408704709982LL;

  std::cout << "Fattorizzazione per tentativi di " << n << " = ";
  rq = radice_quadrata(n);
  m = dividi_per_tentativi(n, rq, basi, esponenti);
  std::cout << m << std::endl;
  std::cout << "Sono state necessarie " << iterazioni << " iterazioni";
  std::cout << std::endl;
}