FFA: Fermat Factoring Algorithm (Algoritmo de Fatoração de Fermat)

Procedimento simples de fatoração inventado por Pierre de Fermat:

Todo numero pode ser escrito como diferença de dois números elevados ao quadrado:

n = a² - b², ou n = a*a - b*b;

Esta expressão pode ser escrita como n = (a+b) * (a-b), ou n = (a+b) (a-b), onde a soma e a subtração dos valores "a" e "b" são dois fatores do número em questão.

Se n é primo, então a-b = 1 e a+b=n;

Para números com diversos fatores e divisores existem diversos "a" e "b" que satisfazem a expressão.

Este algoritmo testa em progressão diversos valores "b" em "i + j*j", ou i + j², com i=n no primeiro passo.

Se i + j*j for um quadrado perfeito, entao calcula-se com base nisto os correspondentes a e b da expressão anterior, tendo-se então encontrado um fator.

Fator este que não é necessariamente um número primo.

Obs[1]: Possível otimizá-lo. Este fica a exemplo de contexto.

Obs[2]: Compilar com a seguinte linha de comando:
(bem lembrado pela moderação) :-)

gcc fermat001.c -o fermat001 -lm

-lm faz ligação com a libm, biblioteca de funções matemáticas do C.

• Download fermat001.c
• Enviar nova versão

Esconder código-fonte

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

/*

Compilar com a seguinte linha de comando:
gcc fermat001.c -o fermat001 -lm

Procedimento simples de fatoracao 
inventado por Pierre de Fermat:

Todo numero pode ser escrito como diferenca de
dois numeros elevados ao quadrado:

n = a*a - b*b;

Esta expressão pode ser escrita como 
n = (a+b) (a-b), onde a soma e a subtracao sao 
dois fatores do numero em questao.

Se n eh primo, a-b = 1, a+b=n;

Para numeros com diversos fatores e divisores
existem diversos a e b que satisfazem a expressao.

Este algoritmo testa em progressao diversos valores "b" em
i + j*j, com i=n no primeiro passo.

Se i + j*j for um quadrado perfeito, entao calcula-se com base 
nisto os correspondentes a e b da expressoo anterior, tendo-se entao 
encontrado um fator.

Fator que nao é necessariamente um numero primo.

*/

typedef unsigned long int ulint;

#define VALOR         48292699

ulint fator (ulint n) {

   if (!n) return 0;         // caso n = 0
   if (!(n>>1)) return 1;         // caso n = 1
   if (~n&1) return ((n>>1)>2?2:(n>>1));   // caso n par

   ulint i=n, j=0, k=0;

   do {

      i += j;
      k = (int) sqrt((double)i);
      j += ((!j)?1:2);      // ainda ha como reduzir pela metade
                  // o numero de repeticoes deste laco

   } while (i-k*k>0);

   k += (j-1)>>1;
   n /= k;

   return (n>k?k:n);

}

int main (void) {

   ulint n = VALOR;
   ulint p=1, q=1;

   do {

      p = fator (n);

      do {   // este loop usa o fator encontrado anteriormente e se
         // assegura de que ele seja o menor 
         q = fator (p); 
         p /= q;
      } while (q>1);

         // isto faz perder tempo, mas não retorna fatores compostos

      n /= p;

      if (p!=1) printf ("%u ", p);
      else printf ("%u\n", n);

   } while (p>1);

   return 0;

}

A tabuada em C!

Google Code Jam 2010 - Africa Classification Round A

Ejetor

Tabela Hash feita em C

Método de Newton Modificado p/ Raízes Multiplas