#include <iostream>
 
 
 
using namespace std;
 
 
 
bool isPrime(int n);
 
 
 
int main()
 
{
 
    int n;
 
 
 
	cout << "Please enter a positive integer to be tested: ";
 
	cin >> n;
 
	cout << "\nYou entered n = " << n << endl;
 
 
 
	if ( isPrime(n) ) 
		cout << "\nIterative isPrime retuned TRUE\n\n";
	else
		cout << "\nIterative isPrime retuned FALSE\n\n";	
 
	return ( EXIT_SUCCESS );
 
}
 
 
 
// Iterative Primality Tester Algorithm
 
// Input: Positive integer n >=2
 
// Output: true if n is prime
//         false if n is composite
 
bool isPrime(int n)
 
{
 
	int i;
 
 
 
	if ( n < 2 )
	{
		cout << "The number entered is less than 2!\n"; 
	    exit(EXIT_FAILURE);
	} 
 
 
	for (i = 2; i < n; i++)
		if ( ( n % i ) == 0 ) return false;
 
	return true;
 
}

#include <iostream>
 
 
 
using namespace std;
 
 
 
bool isPrime(int n);
bool searchFactor(int range, int n);
 
 
 
int main()
 
{
 
    int n;
 
 
 
	cout << "Please enter a positive integer to be tested: ";
 
	cin >> n;
 
	cout << "\nYou entered n = " << n << endl;
 
 
 
	if ( isPrime(n) ) 
		cout << "\nRecursive isPrime retuned TRUE\n\n";
	else
		cout << "\nRecursive isPrime retuned FALSE\n\n";
 
	return ( EXIT_SUCCESS );
 
}
 
 
 
// Recursive Primality Tester Algorithm
 
// Input: Positive integer n >=2
 
// Output: true if n is prime
//         false if n is composite
 
bool isPrime(int n)
 
{
 
	int i;
 
 
 
	if ( n < 2 )
	{
		cout << "The number entered is less than 2!\n"; 
	    exit(EXIT_FAILURE);
	} 
 
 
	return !searchFactor(2, n);;
 
}
 
 
 
// Recursive search for factors 
 
// Input: Positive integer n >=2
//        Positive integer range
 
// Output: true if exists an integer in [range, n-1] that is a factor of n (i.e., n is not prime)
//         false if there is no such integer
bool searchFactor(int range, int n)
{
	if ( range >= n ) return false;
 
	if ( ( n % range ) == 0 ) return true;
	else return searchFactor(range+1, n);
}