/*********************************************************
*   Divisione per Tentativi
*
*   Languasco & Zaccagnini, Introduzione alla Crittografia, Hoepli.
*   Capitolo 6.5.1 pag. 175 
*********************************************************/  

/* input: n - numero di cui si ricerca un fattore
 * output: FALSO o VERO (VERO significa che n e' primo)
 * Dopo aver verificato che n non e` pari si prova a dividere
 * per ogni intero dispari minore o uguale della radice
 * quadrata di n.
 */

{Trialdivision(n) = local (TRUE,FALSE, iterazioni);
        TRUE=1;
        FALSE=0;
        iterazioni=0;
        if(n % 2 == 0,
                print("Il numero ", n," e` pari");
                iterazioni=iterazioni+1;
                print("Il numero totale di iterazioni e` ", iterazioni);
                return(FALSE);
        );
        forstep (m=3,floor(sqrt(n)),2,
                iterazioni=iterazioni+1;
                if (n%m==0, 
                        print(m," divide ",n);
                        print("Il numero totale di iterazioni e` ", iterazioni);
                        return(FALSE)
                )
        ); 		
        print(n, " e` un numero primo");
        print("Il numero totale di iterazioni e` ", iterazioni);
        return(TRUE);
}