Algoritmo de Fatoração de Fermat (FFA) em Perl
Publicado por Perfil removido (última atualização em 17/05/2012)
[ Hits: 8.916 ]
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]: Ainda é possível melhorá-lo.
Obs[2]: Números negativos são desconsiderados para simplificação. Por enquanto.
#!/usr/bin/perl use warnings; use strict; my $VALOR = 3*5*7*3*11*31*43*31; sub fator { my $n = shift; return (-1, 1) if ($n<0); return (0, 1) if (!$n); return (1, 1) if (!($n>>1)); return (($n>>1),2) if (~$n&1); my ($i, $j, $k) = ($n, 0, 0); do { $i += $j; $k = int sqrt($i); $j += ((!$j)?1:2); } while ($i-$k*$k>0); $k += ($j-1)>>1; $n /= $k; return (($n>$k?$n:$k),($n<$k?$n:$k)); } my @fatores1 = ($VALOR); my $p = 1; foreach (@fatores1) { do { ($_, $p) = fator($_); push (@fatores1, $p) unless ($p==1); } until ($p<=1); } my @fatores2 = sort { $a <=> $b } (@fatores1); foreach (@fatores2) { print "$_ "; } print "\n";
Ler uma sequências fasta e separar por tamanho [Bioinformática]
Calculadora de notas versão Perl
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
Um modo leve de ouvir/ver áudio/vídeo da internet em máquinas pererecas
Resolver algumas mensagens de erro do SSH
Instalar módulo de segurança do Banco do Brasil Warsaw do tipo .run
Sem espaço na partição home (1)
O que você está ouvindo agora? [2] (190)
Procrastinação e autossabotagem são problemas muito comuns na sociedad... (5)
warsaw parou de funcionar após atualização do sistema (solução) (10)