#include <stdio.h>
#include <math.h>

int lucas_lehmer(unsigned int p)
{
    unsigned int s = 4;
    unsigned int M = pow(2,p) - 1;
    unsigned int i;

    for(i = 0; i < p-2; i++)
        s = ((s * s) - 2) % M;

    return s == 0;
}

int main(int argc, char *argv[])
{
    if(argc != 2)
    {
        printf("usage: %s prime\n", argv[0]);
        return 0;
    }
    unsigned int p = atoi(argv[1]);

    unsigned int s = lucas_lehmer(p);

    printf("2 ^ %d - 1 is %s\n", p, s ? "prime" : "not prime");
    return 0;
}