The New Stuff

C/C++: Algoritmo de Fatoração de Fermat (FFA) em 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.


Viva o Linux

Recently Published

article image
»

Ubuntu no Palito: Intel Compute Stick com Linux vai custar US$ 110

O Intel Compute Stick parece um pen drive, mas pluga numa entrada ...

article image
»

Ubuntu no Palito: Intel Compute Stick com Linux vai custar US$ 110

O Intel Compute Stick parece um pen drive, mas pluga numa entrada ...

article image
»

Cisco comprando o OpenDNS

Há muito tempo eu não uso os servidores do OpenDNS, mas ainda ...

article image
»

Resolução de problemas no Docker

Enviado por Rafael Gomes (gomexΘriseup·net): “O Docker é uma ...

article image
»

Lançado Linux Mint 17.2 Rafaela

Enviado por Marcos Paulo de Souza ...

article image
»

Veja como instalar o cliente não oficial do WhatsApp no Ubuntu, Debian e derivados

Enviado por Edivaldo Brito (edivaldobezerraΘgmail·com): “Foi ...

article image
»

Navegador Chromium faz download de módulo proprietário que ouve pelo microfone e manda para o Google

Quem usa o Chromium (versão alternativa do Chrome) por ver nele os ...

article image
»

Novatec Editora lança livro Programação de Redes com Python

Enviado por Stephanie Milate (smilateΘnovatec·com·br): “Novo ...

article image
»

WeeChat – Um (o) cliente IRC CLI

Enviado por Gildásio Júnior (gildasio97Θgmail·com): “IRC foi ...