#include <stdlib.h>
#include <stdio.h>
#include <gmp.h>

int
isprime(unsigned long p)
{
  unsigned long d;
  if ( p <= 1 ) return(0);
  if ( p == 2 ) return(1);
  if ( p % 2 == 0 ) return(0);
  for ( d = 3 ; d*d <= p ; d += 2 ) { if ( p % d == 0 ) return(0); }
  return(1);
}

int
main(int argc, char *argv[])
{ 
  unsigned long pmin, pmax, p, i;
  mpz_t ll, lll, llu, aux;

  mpz_init(ll);
  mpz_init(lll);
  mpz_init(llu);
  mpz_init(aux);     /* Inicializamos as variáveis pp, ll e aux. */

  pmin = atol(argv[1]);
  pmax = atol(argv[2]); /* Lemos pmin e pmax. */

  for ( p = pmin ; p <= pmax ; p++ )
  if ( isprime(p) )
  {
  if ( p == 2 ) { printf("M2 é primo.\n"); continue; }

  mpz_set_ui(ll,(long)(4));
  
  for ( i = 1 ; i + 2 <= p ; i++ )
  {
    mpz_mul(aux,ll,ll); 
           /* Elevamos ll ao quadrado ... */
    mpz_fdiv_q_2exp(llu,aux,p);
    mpz_fdiv_r_2exp(lll,aux,p);
    mpz_add(aux,llu,lll);
    mpz_fdiv_q_2exp(llu,aux,p);
    mpz_fdiv_r_2exp(lll,aux,p);
    mpz_add(aux,llu,lll);
           /* tomamos o resultado modulo Mp ... */
    mpz_sub_ui(ll,aux,(long)(2)); 
           /* ... e subtraimos 2, para calcular s(p-2) modulo Mp. */
    /* mpz_out_str(stdout,10,ll); fprintf(stdout,"\n"); */
  }

  if ( mpz_sgn(ll) == 0 )
  { printf("M%ld é primo.\n",p); }
  else
  { printf("M%ld é composto.\n",p); } /* Imprimimos as conclusões. */

  }

  return(0);
}