/* 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 */ }