Esercizio 4        

Scrivere un programma che sia in grado di stabilire se un dato numero intero è primo oppure no, utilizzando la ricorsione senza usare i cicli.
Una possibile soluzione per risolvere il test di primalità per un numero intero maggiore di 1 è la seguente:

#include<iostream>
using namespace std;

bool isp(int i, int n){
   cout<<i<<"\t "<<n%i<<endl;
   return n%i==0 ? n==i : isp(i+1,n);
}//isp

main(){
   int num;
   cout<<"ins.num:";cin>>num;
   isp(2,num) ? cout<<"primo" :cout<<"NON primo";
}//main

Un numero primo è divisibile solo per 1 e per se stesso.
Premesso ciò, la funzione
isp(int i, int n)
riceve un intero i inizialmente uguale a 2 ed il numero n di cui si desidera stabilire la natura. L’istruzione
return n%i==0 ? n==i : isp(i+1,n);
Determina il comportamento ricorsivo della funzione.
La ricorsione si arresta quando la divisione di (n) per (i) fornisce resto zero e questo accade in ogni caso.
Se la divisione fornisce resto non nullo la funzione richiama se stessa incrementando i. Quando il resto n%i è zero, il risultato della comparazione (n==i) restituisce 1(vero) se il numero è primo altrimenti restituisce 0(falso) se il numero non è primo.