/*
 * mersenne.c - find the first Mersenne prime greater than 1000.
 * Note that it is not the 'n' which is greater than 1000, it is the 2**n-1.
 *
 * Algorithm: Search for the first 2**n-1 which is greater than 1000, then
 * increment n from there until we get a prime 2**n-1.
 *
 * This illustrates partial memoization in power2(), below.
 */

#include <stdio.h>


int main()
{
    int n;
    extern int isprime(int p), power2(int n);

    /* First, find the least n such that 2**n-1 > 1000. */
    for (n = 1; power2(n) <= 1000; n++)
        ;

    /* now, keep going until we have a Mersenne prime */
    for (; !isprime(power2(n) - 1); n++)
        ;

    printf("2**%d-1 is %d, which is prime\n", n, power2(n) - 1);

    return 0;
}



/*
 * return 2**n for n>=0.  Avoids redoing all that multiplying if the 'n'
 * is the same as the last n, and avoids unnecessary re-multiplying if the
 * 'n' is greater than the last one (it will often be the previous n plus 1).
 */
int power2(int n)
{
    static int lastn = 1;
    static int lastpower2 = 2;  /* 2**n */

    if (lastn > n) {
        lastn = 0;
        lastpower2 = 1;
    }

    for (; lastn < n; lastn++)
        lastpower2 *= 2;

    return lastpower2;
}


/*
 * return true or false to indicate whether p is prime.
 * p must be >= 2.
 */
int isprime(int p)
{
    int d;

    for (d = 2; d < p; d = d + 1)
        if (p % d == 0)
            return 0;

    return 1;
}