#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

bool is_number_in_array(int n, int const* array, size_t len) { // using binary search
    if(len == 0) {
        return false;
    }
    else if(len == 1) {
        return (array[0] == n ? true : false);
    }
    else {
        size_t len_0 = (len + 1) / 2;
        size_t len_1 = len / 2;
        int const* sub_array_0 = array;
        int const* sub_array_1 = array + len_0;
        assert(len_0 + len_1 == len && len_0 < len && len_1 < len);  // sanity checks
        if(n < sub_array_1[0]) {
            return is_number_in_array(n, sub_array_0, len_0);
        }
        else {
            return is_number_in_array(n, sub_array_1, len_1);
        }
    }
}

int main(int argc, char* argv[]) {
    int const primes[] = { 2, 3, 5, 7, 11, 13, 17, 19 };    
    size_t num_primes = sizeof primes / sizeof primes[0];  // ONLY works for static [] array
    for(int n = 0; n < 20; n++) {
        bool is_prime = is_number_in_array(n, primes, num_primes);
        printf("%d %s prime\n", n, (is_prime ? "is" : "is NOT"));
    }
    return EXIT_SUCCESS;
}
/* vim: set tabstop=4 shiftwidth=4 fileencoding=utf-8 noexpandtab: */