isPrime recursive

#include <iostream>
using namespace std;

int increments[] = { 2, 4 };

// Already beyond the square root? -> true (prime)

// (else)

// Divisible by current divisor?   -> false (not prime)

// (else)

// Calculate next divisor and recurse
bool isPrime(int n, int divisor, int incr) {
   return (divisor * divisor > n ) || 
          ( (n % divisor != 0) && 

            isPrime(n, divisor + incr, increments[incr == 2] )

          );
}
 
bool isPrime(int n) {
    return isPrime(n, 2, 1);
}

int main()
{
    for(int i = 2; i <= 100; i++ ) {
        if( isPrime(i) ) {
            cout << i << " ";
        }
    }
    cout << endl;

    return 0;
}

Other entries:

• isPrime: Naive version 
• isPrime, Optimization 1: Iterate only until the square root of the number
• isPrime, Optimization 2: Only divide by odd numbers, until the square root of the number
• isPrime, Optimization 3: Skip the divisors that are multiple of 2 or 3
• Keep the previosly generated primes and use them to test the following numbers.
• isPrime, Recursive.