The New Stuff

Outros: Algoritmo de Fatoração de Fermat (FFA) em Ruby


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

Método 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, então 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.

Este programa trabalha com os fatores sendo escritos em uma lista, sendo pegos um a um até o final.

A função de fatoração retorna uma estrutura com um par de números que se multiplicados retornam o valor de entrada, ordenados em maior e menor.

No retorno, a parcela menor substitui a posição do elemento pego anteriormente e a parcela maior é inserida ao fim da lista principal.

Quando o valor menor do par é um, o valor maior é um número primo, então continua-se com o próximo elemento da lista principal, encerrando-se ao último elemento.

Por último, a lista de fatores é ordenada para apresentação.

Obs[1]: Por enquanto não fatora números negativos.
Obs[2]: É possível ainda um teste que reduz o número de repetições do while da sub-rotina.


Viva o Linux

Recently Published

article image
»

15% OFF até 05/02 – Curso de Elastix em São Paulo – 16 a 18/02/16 Confirmado

O aluno realizará na prática a criação e configuração de uma ...

article image
»

Lançamento do Livro GIMP Descomplicado

Após anos percorrendo o Brasil e exterior lecionando diversos ...

article image
»

Livro Shell Linux e site sobre livros de Linux

Eu, Tales Mendonça e Bruno Gonçalves, gostaríamos de anunciar o ...

article image
»

GPUOpen – a revolução dos drivers de vídeo para Linux

No final do ano passado, a AMD anunciou o GPUOpen; um conjunto de ...

article image
»

Ginástica via SSH: como substituir o Debian pelo Arch em uma máquina remota (rodando)

Para quem gosta de aventuras e ginástica na linha de comando remota, ...

article image
»

Python: 2º Encontro Pyladies Floripa é neste sábado

A Melissa Weber Mendonça avisa que amanhã tem Encontro Pyladies em ...

article image
»

openCertiface 1.0: biometria facial, com exemplos em C, PHP, Java e Bash

O openCertiface é a versão de código aberto do serviço de ...

article image
»

Escrevendo um jogo para MSX usando Linux

Esta está no meio do caminho entre o BR-Linux e o BR-Arduino. Em ...

article image
»

Na Holanda, defesa do consumidor processa Samsung para obrigar a prover 2 anos de atualizações para Android

Após verificar que 82% dos smartphones Samsung vendidos no país ...