Jump to content
fredericopissarra

Uma otimização interessante para testar se um valor é primo

Recommended Posts

Artigo original: https://is.gd/sDQ7Oa

Esse é um dos exercícios mais comuns na área acadêmica: Dizer se um número é primo ou não. Existe a maneira tradicional, a maneira rápida e a maneira super rápida… As duas primeiras eram minhas velhas conhecidas e já falei delas aqui, eis um resumão:

O método tradicional é dividir todos os valores inferiores ao número n, sob teste, até chegarmos a 2 e se o resto de qualquer uma das divisões der zero, isso indica uma divisibilidade e, portanto, o valor não é primo:

int isPrime( unsigned int n )
{
  unsigned int i;
 
  // casos especiais... 3 e 2 são primos, mas 1 e 0 não são!
  if ( n <= 3 )
    return ! ( n < 2 );
 
  for ( i = 2; i < n; i++ )
    if ( ( n % i ) == 0 )
      return 0;
  
 return 1;
}

O método rápido reduz o a quantidade de iterações do loop porque só precisamos verificar a divisibilidade de valores inferiores ou iguais à raiz quadrada de n. Isso é baseado na propriedade comutativa e do princípio fundamental da aritmética: 2*3 é a msma coisa que 3*2, então não precisamos testar os dois casos. Ainda, qualquer valor pode ser fatorado em primos… Outro detalhe importante para o teste é que só existe um valor par primo: 2, todos os demais são ímpares:

int isPrime( unsigned int x )
{
  unsigned int i, s;
 
  if ( n <= 3 )
    return ! ( n < 2 );
 
  // Apenas 2 é um valor par primo!
  if ( n % 2 == 0 ) 
    return 0;

  // Só precisaremos testart até a raiz quadrada...
  s = sqrt(n);
 
  // Não precisamos testar a divisibilidade por nenhum valor par.
  for ( i = 3; i <= s; i += 2 )
    if ( ( n % i ) == 0 )
      return 0;
 
  return 1;
}

Quando você acha que achou o código mais rápido possível algum detalhe te supreende. O código acima pode ser acelerado um bocado se pensamos que se o valor n é divisível por 6, então ele é divisível por 3 e por 2 e, portanto, não é primo. De outro modo, podemos retirar valores que, divididos por 6, resultam em restos 2, 3 ou 4, já que, com toda certeza, eles não são primos (ou são divisíveis por 2 ou 3):

int isPrime(unsigned int n)
{
  unsigned int i, s;
 
  if (n <= 3)
    return ! ( n < 2 );
 
  // Mais um caso especial... Se for divisível por 2 ou 3, não é primo!
  if ( ( n % 2 ) == 0 || ( n % 3 ) == 0)
    return 0;
  
  s = sqrt(n);
  
  for ( i = 5; i <= s; i += 4 )
  {
    if ( ( n % i ) == 0)
      return 0;
 
    i += 2
 
    if ( ( n % i ) == 0)
      return 0;
  }
 
  return 1;
}

O código acima executa o loop cerca de 3 vezes mais rápido que o código anterior e é matematicamente correto. Claro, existe o problema de que duas divisões são feitas no loop, mas o compilador tende a otimizar isso…

PS: Lembrando que existe um outro método, rápido, mas que consome muita memória: Trata-se do “Crivo de Eastótenes” que encontra os valores primos tentando as divisões com os valores primos anteriormente encontrados (até a raiz quadrada de n, como acima)… O “Crivo” é o método mais rápido, mas como eu disse, tem o potencial de consumir MUITA memória, porque precisamos manter um array com os valores previamente encontrados.

Edited by fredericopissarra
  • Curtir 1

Share this post


Link to post
Share on other sites

PS: Eu não pensei nesse terceiro método. Ele me foi apresentado num forum, onde duvidei bastante da "correção" matemática dele. Mas, acaba que o troço tá certo mesmo... Vivendo e aprendendo...

Share this post


Link to post
Share on other sites
Em 02/11/2019 em 11:10, fredericopissarra disse:

PS: Eu não pensei nesse terceiro método. Ele me foi apresentado num forum, onde duvidei bastante da "correção" matemática dele. Mas, acaba que o troço tá certo mesmo... Vivendo e aprendendo...

Muito interessante, acho que consigo explicar como funciona de uma forma complementar.

 

Esse algoritmo pula os ímpares múltiplos de três no momento que incrementa quatro no contador (i+=4) , a partir do número nove, visto que a divisibilidade por três já foi testada.

 

Desta forma:

testa o 5; // valor inicial

testa o 7; //após incrementar i+=2

pula o 9; //ao incrementar i+=4

testa o 11; //após incrementar i+=4

testa o 13; //após incrementar i+=2

pula o 15; //ao incrementa i+=4

testa o 17; //após incrementar i+=4

testa o 19; //após incrementar i+=2

pula o 21; //ao incrementa i+=4

... e assim por diante.

Note que comparado a abordagem que você descreveu anteriormente, em um ciclo de três testes (if ( ( n % i ) == 0) ) um teste é eliminado . Assim, é possível eliminar 1/3 dos testes a serem executados.

Edited by trevizan

Share this post


Link to post
Share on other sites

Poxa eu achei o Tio Fred de novo...eu tava no grupo do facebook dele e voltei a estuar comp esse semestre agora estou apenas nos mips da vida.

Muito bom te achar aqui tio fred.

  • Haha 1

Share this post


Link to post
Share on other sites

Já eu, @bratergames, nunca parei de estudar e estou com os ARM da vida, mas não "apenas"... 🙂
Tio Fred só sumiu do facebook (nunca mais entro naquela bosta) e do discord do mente binária...

Share this post


Link to post
Share on other sites

Olás!

Fiquei pensando como seria estender a estratégia de eliminar os testes de ímpares múltiplos de três para também eliminar os testes dos múltiplos de cinco.

Cheguei ao seguinte algoritmo. Este executa cerca de 13% mais rápido que o algoritmo anterior e cerca de 47% mais rápido que o algoritmo que só considera a raiz quadrada.

int isPrime(unsigned int n)
{
  unsigned int i, s;

  if (n <= 5)
    return (n  == 2 || n == 3 || n == 5);

 
  // Mais um caso especial... Se for divisível por 2, ou por 3, ou por 5, não é primo!
  if ( ( n % 2 ) == 0 || ( n % 3 ) == 0 || ( n % 5 ) == 0)
    return 0;

  s = sqrt(n);


  for ( i = 7; i <= s; i += 6 )
  {

    if ( ( n % i ) == 0)
      return 0;
   
    i += 4;
    if ( ( n % i ) == 0)
      return 0;
  
    i += 2;
    if ( ( n % i ) == 0)
      return 0;
  
    i += 4;
    if ( ( n % i ) == 0)
      return 0;
  
    i += 2;
    if ( ( n % i ) == 0)
      return 0;
  
    i += 4;
    if ( ( n % i ) == 0)
      return 0;
  

    i += 6;
    if ( ( n % i ) == 0)
      return 0;
  
    i += 2;
    if ( ( n % i ) == 0)
      return 0;
  
  }
 
  return 1;
}

 

Share this post


Link to post
Share on other sites

Well... Talvez, temos que verificar (a validade do algoritmo anterior é um cadinho mais complicada do que eu postei - desse ai, eu não sei)...
Mas, de qualquer maneira, temos que parar em algum lugar, não? Senão o algoritmo degenera para o crivo de Erastótenes.

Share this post


Link to post
Share on other sites

Basicamente eu vi quais valores  precisavam ser testados (os que não eram múltiplos de 2, 3 ou 5) a partir do número 7 e notei que essa sequência de incremento se repetia (como um padrão):

4, 2, 4, 2, 4, 6, 2 e 6.

Validei os resultados de 2 a pouco mais de 32 mil e não apresentou nenhum  retorno incorreto para o intervalo. 

 

Enfim,  o problema é que a complexidade de todos esses algoritmos ainda é da ordem de grandeza de raiz quadrada de n, ou seja,  ainda é alta.

 

Eu preciso estudar melhor o crivo de Erastótenes para opinar,  mas a primeira vista a abordagem me parece bem diferente e o ganho de desempenho não compensa a limitação de valor máximo que pode ser testado.

Daí talvez seja mais interessante brincar com coisas mais sérias, como o teste de Fermat ou AKS, que apresentam complexidade logarítmica.

Edited by trevizan

Share this post


Link to post
Share on other sites

Não estou dizendo que sua aproximação está errada ou que seja ruim. Só o que estou dizendo é que, talvez, ela possa falhar em algum momento. Limitar os testes a uma faixa que "dá certo" não quer dizer que o algoritmo vai funcionar para toda a faixa... A otimização que postei (que não foi minha, vi num forum e achei interessante) funciona para qualquer valor N, inteiro, de qualquer precisão...

O sujeito que bolou isso percebeu que quando um valor é primo e é maior que 4, ele pode ser expresso por 6n+/-k (onde k={0..5}, ou seja, k=n mod 6)... mas, k não pode ser 0, 2, 3 ou 4 (senão teremos valor par [k=0,2,4] ou divisível por 3 [k=3]). Assim, k só pode ser 1 ou 5. Agora, tomemos n=1 e obteremos 5 (6*1-1) e 7 (6*1+1), e 1 (6*1-5) e 11 (6*1+5). Esses são candidatos a primazia... Se você fizer n=2 (n+1), teremos 11 (6*2-1), 13 (6*2+1), 7 (6*2-5) e 17 (6*2+5). Claramente (e podemos comprovar isso por congruência) testes com k=5 são cobertos pelos mesmos testes onde k=1 e podemos descartar k=5.

Dai, o testes de primazia só precisam ser feitos com 6n-1 e 6n+1. Por isso o loop começa em 5, avançamos k em 2 unidades (de -1 para +1), testamos o próximo e testamos de novo... avançamos 4 unidades (por causa do 6n) e fazemos tudo de novo...

O que descrevi acima é uma prova por "indução matemática" e é garantido que o resultado seja o mesmo para qualquer N... Teríamos que provar, de maneira semelhante, que sua aproximação é válida para qualquer N inteiro positivo e é isso que eu não tenho certeza (porque não pensei à respeito) que esteja correto.

Quanto ao crivo de Erastótenes. Basicamente ele realiza as divisões apenas com os valores prímos previamente encontrados, no loop, mas precisa armazená-los num grande array. Esse é o método mais "rápido" (e um pouquinho mais complicado), mas potencialemente usa muita memória para isso. No caso, mesmo não usando arrays, a cadeia de testes ficaria muito grande e é bom lembrar que cada divisão é LENTA. Uma rotina com 2 divisões não é cria lá grande perda de velocidade, mas uma com 8 divisões dentro do loop tem o potencial de ser bem lenta.

[[]]ão
Fred

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.


  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...