Re: Programa_para_achar_nºs_primos_...

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxxxxxxxxx>]

--- Eleu Lima Natalli <eleu.vix@zaz.com.br> escreveu:
> Alguem sabe em q site posso baixar o prog q ''caça''
>  nº primos ?

Não sei bem o que você tem em mente, mas em
www.mersenne.org
você pode baixar um programa que procura primos de Mersenne,
leia mais lá sobre o assunto. O programa abaixo gera primos de Proth,
primos da forma a*2^b + 1 (com a relativamente pequeno). Exemplo:

boto:~/papers/mersenne/prog%./proth1a 1 500 120
7 * 2^120 + 1 = 9304595970494411110326649421962412033 é primo.
231 * 2^120 + 1 = 307051667026315566640779430924759597057 é primo.
277 * 2^120 + 1 = 368196154832421696794354555697655447553 é primo.
315 * 2^120 + 1 = 418706818672248499964699223988308541441 é primo.
331 * 2^120 + 1 = 439974466604807153931160136952794054657 é primo.

Acabei de rodar este exemplo e não demorou nada perceptível.
O exemplo abaixo demorou poucos segundos.

boto:~/papers/mersenne/prog%./proth1a 1 1000 500
711 * 2^500 + 1 = 2327380722214156869579377874444422997226032494736619065322620162716351129243723608522005035643717855734280432414695210487553469404124514460916583116046337 é primo.

Note que estes números são _demonstravelmente_ primos e não
apenas _provavelmente_ primos.

Eu compilei o programa assim:

boto:~/papers/mersenne/prog%gcc proth1.c -lm -lgmp -Wall -o proth1a

Isto em uma máquina Linux. Deve ser fácil fazer o programa funcionar
em OS parecidos com Unix e deve ser possível até em Windows.

Há mais coisa deste tipo no livro do Gugu e meu sobre primos de Mersenne,
disponível na minha home page.

[]s, N.

=======================================================================


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

mpz_t pp; 

int
proth(unsigned long h, unsigned long k)
{
  unsigned long i;
  mpz_t pm, test, aux;
  extern mpz_t pp;  
  
  mpz_init(pm);
  mpz_init(test);
  mpz_init(aux);    

  mpz_ui_pow_ui(pm,(long)(2),k);
  mpz_mul_ui(pm,pm,h);
  mpz_fdiv_q_2exp(aux,pm,(long)(1)); 
  mpz_add_ui(pp,pm,(long)(1)); 
  /* Calculamos pp = hh * 2^k + 1, pm = pp - 1 e aux = (pp-1)/2. */

  mpz_set_ui(test,(long)(2));
  mpz_powm(test,test,aux,pp); 
  if ( mpz_cmp(test,pm) == 0 )
  {
    mpz_clear(pm);
    mpz_clear(test);
    mpz_clear(aux);    
    return(1);
  }
  if ( mpz_cmp_ui(test,(long)(1)) != 0 )
  {
    mpz_clear(pm);
    mpz_clear(test);
    mpz_clear(aux);    
    return(0);
  }

  for ( i = 3 ; i < 1000 ; i += 2 )
  {
    mpz_set_ui(test,i);
    if ( mpz_probab_prime_p(test,25) )
    {
      mpz_powm(test,test,aux,pp); 
      if ( mpz_cmp(test,pm) == 0 )
      {
        mpz_clear(pm);
        mpz_clear(test);
        mpz_clear(aux);    
        return(1);
      }
      if ( mpz_cmp_ui(test,(long)(1)) != 0 )
      {
        mpz_clear(pm);
        mpz_clear(test);
        mpz_clear(aux);    
        return(0);
      }
    }
  }

  mpz_clear(pm);
  mpz_clear(test);
  mpz_clear(aux);    
  return(-1);
}

int
main(int argc, char *argv[])
{ 
  int answ;
  unsigned long h, hmin, hmax, k;
  extern mpz_t pp;

  hmin = atol(argv[1]);
  hmax = atol(argv[2]);
  k = atol(argv[3]);
  mpz_init(pp);

  for ( h = hmin ; h <= hmax ; h++ ) if ( h & 1 )
  {
    answ = proth(h,k);
    if ( answ == 1 )
    {
      printf("%ld * 2^%ld + 1 = ",h,k);
      mpz_out_str(stdout,10,pp);
      printf(" é primo.\n");
    }
    else if ( answ < 0 ) printf("%ld * 2^%ld + 1: difícil...\n",h,k);
  }

  return(0);
}

=========================================================================