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
»

FAP – Dia do Software Livre – 18 de setembro de 2015

Enviado por Raimundo Xavier (xavier·raimundoΘgmail·com): “Dia 18 ...

article image
»

Linuxfx 7.3 + Biometria disponível para download

Enviado por Rafael Wagner (rafaelΘlinuxfx·org): “É com muito ...

article image
»

Apple lança o CUPS 2.1.0, agora com suporte a impressora 3D, novos recursos para impressão criptografada, e mais

A versão 2.1.0 do CUPS, o sistema de impressão da Apple com suporte ...

article image
»

Saiu o kernel Linux 4.2

Linus Torvalds anunciou o lançamento da versão 4.2 do seu kernel ...

article image
»

Virsh: criando e gerenciando VMs pelo terminal

Virsh! Enviado por Marcos Paulo de Souza ...

article image
»

Qt 5.5 adiciona novos módulos e amplia o suporte multiplataforma

Via www.infoq.com: o novo release do Qt 5.5 corrigiu quase 1500 bugs ...

article image
»

Firefox poderá rodar plugins do Chrome e Opera de maneira mais fácil

O título acima é da matéria da PC World. No LinuxToday saiu como ...

article image
»

Instalando o Zabbix Server e Zabbix Agent no Raspberry Pi

Enviado por Marcos Vinícius Campez (marcosΘbytelivre·net): “Olá ...

article image
»

Tudo que você queria saber sobre processadores de texto II, a Missão

Enviado por Juan Carlos Castro (jccyc1965Θgmail·com): “O podcast ...