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.

• Download fermat001.pl
• Enviar nova versão

Esconder código-fonte

#!/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";

Auto Ident XML

Sem Queda 2.0

lol

htt[p]erl, simulador de web server

Introdução a Persistência de Estrutura de Dados em Perl