Algoritmo de Fatoração de Fermat (FFA) em Ruby
Publicado por Perfil removido (última atualização em 21/06/2012)
[ Hits: 5.513 ]
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.
#!/usr/bin/ruby VALOR = 3*5*7*3*11*31*43*31 #VALOR = 2*2*2*2*2*2*2*2 #VALOR = 984*365*5*36*3*275*257*4257*4258*24890 def fator n return [-1, 1] if n<0 return [0, 1] if n==0 return [1, 1] if n==1 return [2, 1] if n==2 return [n>>1,2] if ((n%2)==0) i, j, k = n, 0, 0 i += j and k = (i**(0.5)).to_i and j += ((j==0)?1:2) while (i-k*k>0) k += (j-1)>>1; n /= k; return [n,k] if n>=k return [k,n] if n<k end fatores1 = [VALOR] p, q = 1, 0 while q<fatores1.length do while p>=1 do fatores1[q], p = fator(fatores1[q]) p==1 ? break : fatores1 += [p] end q += 1 end (fatores1.sort).each do |i| print i, " " end puts
Uso simples de if e else em Ruby
Exportar endereços do Evolution para vCard
Agenda telefônica em Ruby que grava os dados em um txt
Importar endereços do Claws no Evolution (entre outros)
Atualizando o Passado: Linux no Lenovo G460 em 2025
aaPanel - Um Painel de Hospedagem Gratuito e Poderoso
O macete do Warsaw no Linux Mint e cia
Visualizar arquivos em formato markdown (ex.: README.md) pelo terminal
Dando - teoricamente - um gás no Gnome-Shell do Arch Linux
Como instalar o Google Cloud CLI no Ubuntu/Debian
Mantenha seu Sistema Leve e Rápido com a Limpeza do APT!
Procurando vídeos de YouTube pelo terminal e assistindo via mpv (2025)
Jogos baixados na Central de Aplicativos mas que não abrem (1)
debian com wayland, configuracao de teclado. Mudou Tudo! [RESOLVIDO] (1)
Iinstalar o Scanner Kodak i940 no Linux Mint 19/20? (3)
Pastas da raiz foram para a área de trabalho [RESOLVIDO] (11)