Algoritmo de Fatoração de Fermat (FFA) em C

Publicado por Perfil removido (última atualização em 10/04/2012)

[ Hits: 9.683 ]

Download fermat001.c




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.

  



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;

}

Scripts recomendados

Jantar dos Filósofos - Programação Paralela

Entendendo a função fork()

Stack (LIFO)

QuickSort Genérico

Trabalhando com Matrizes


  

Comentários


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner
Linux banner
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts