Algoritmo de Fatoração de Fermat (FFA) em Ruby
Publicado por Perfil removido (última atualização em 21/06/2012)
[ Hits: 5.237 ]
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
Controle de maior e menor de idade em Ruby
Uso simples de if e else em Ruby
Agenda telefônica em Ruby que grava os dados em um txt
Importar endereços do Claws no Evolution (entre outros)
Como agendar um backup automático do PostgreSQL no Cron evitando o problema de senha
Como preparar o Vim/Neovim para corrigir ortografia em português
Dark Web e Malwares na internet, quanto custa?
Configuração básica do Conky para mostrar informações sobre a sua máquina no Desktop
Como verificar o hash de um arquivo baixado da Internet e como criar um hash
Debian 12 - IPTABLES - removendo NFTABLES
OverWatch 2 - Abrindo portas do jogo no Iptables.
Como instalar o adaptador wifi USB Intelbras ACtion A1200 no Linux Mint
Como normalizar seus arquivos MP3 para que fiquem no mesmo volume
Instalação do Programa Imposto de Renda Pessoa Física 2023 [RESOLVIDO]... (6)
Instalando e compilando o GCC/G++ erro (4)
[C/C++] BRT - Bulk Renaming Tool
[Shell Script] Criação de Usuarios , Grupo e instalação do servidor de arquivos samba
[Shell Script] Tire screenshots com Scrot facilmente com Zscrot
[Shell Script] DioPSI - Script multidistro para instalar programas
[Shell Script] ARS Vídeos - Cortador de vídeos e webcam shooter