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

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 );

  if ( ( n % 2 ) == 0 )
    return 0;

  s = sqrt(n);

  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.