/* File: primrico.c */
/* Time-stamp: "2001-03-27 15:34:12 calvanes" */
/* Scopo: esempio di funzione ricorsiva  */

/* Verifica se due interi sono primi tra loro (cioe` non hanno divisori comuni
   maggiori di 1).

   Utilizza la seguente definizione induttiva:

     primi(x,y) = vero           se x = 1 oppure y = 1    (caso base)
     primi(x,y) = falso          se x = y                 (caso base)
     primi(x,y) = primi(x,y-x)   se x < y                 (caso ricorsivo)
     primi(x,y) = primi(x-y,y)   se x > y                 (caso ricorsivo)
*/

#include <stdio.h>


int primi(int, int );       /* il valore intero restituito e` di tipo booleano
                                 vale 1 se X e Y sono primi tra loro
                                 vale 0 se X e Y NON sono primi tra loro */

int main(void)
{
  int n1, n2 ;

  printf( "Inserisci 2 interi positivi: ") ;
  scanf("%d%d", &n1, &n2);
  if (primi(n1,n2))
    printf("%d e %d sono primi tra loro\n", n1, n2);
  else
    printf("%d e %d NON sono primi tra loro\n", n1, n2);

  return 0;
}


int primi(int x, int y)
{
  if (x==1 || y==1)
    return 1;                     /* sono primi tra loro se uno dei due e` 1 */
  else if (x == y)
    return 0;                     /* se sono uguali non sono primi tra loro */
  else if (x < y)
    return primi(x, y-x);         /* caso ricorsivo */
  else
    return primi(x-y, y);         /* caso ricorsivo */
}