/*
 * mersenne.c - find the first Mersenne prime greater than 1000.
 * A Mersenne prime is a prime number of the form (2**n)-1 for a positive
 * integer n.
 *
 * 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.
 */

#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 */
int power2(int n)
{
    int i, product = 1;

    for (i = 0; i < n; i++)
	product *= 2;
    
    return product;
}